## Problem Description:

Given a positive integer array, find all the elements that have been repeated and display them.

### Example:

Input: {1, 3, 2, 7, 5, 1, 3}

Output: 1, 3

## Solution:

The solution is very simple.

We traverse through the array and make the element in that index as negative. This means the element is unique at that time.

We can achieve that from the below formula:

arr[abs(arr[i])] = -arr[abs(arr[i])];

Here abs( ) will return +ve value of the element.

Then if the same element repeats we check if the element is –ve. If –ve then we take it as a repeated element.

Below is how the algorithm work:

Input: {1, 5, 1, 3}

pass 0: i = 0 arr[ arr [0] ] is -ve ? NO arr[ arr[0] ] = - arr[ arr[0] ]; arr[ 1 ] = -arr [ 1 ]; arr[ 1 ] = -5

pass 1: i = 1 arr[ arr[1] ] is -ve ? NO arr[ arr[1] ] = - arr[ arr[1] ]; arr [ 5 ] = -arr [5] arr [ 5 ] = -5

pass 2: i = 2 arr[ arr[2] ] is -ve Hence this element is repeated.

## Solution in C

#include <stdio.h> #include <stdlib.h> void checkduplicate(int arr[], int length) { int i; printf("The repeating elements are: \n"); for (i = 0; i < length; i++) { if (arr[abs(arr[i])] >= 0) { arr[abs(arr[i])] = -arr[abs(arr[i])]; } else printf(" %d ", abs(arr[i])); } printf("\n"); } int main() { int arr[] = {1, 3, 2, 7, 5, 1, 3}; int length = 7; checkduplicate(arr, length); return 0; }

Output:

The repeating elements are: 1 3

## somename

hashmap for better time complexity.. sort to save space complexity.

## ajay

If you have the solution could you please post it here. I am not aware of the solution. Thanks.

## Nitish

you didn’t told the values will be within the size of array

## Divyanshu Garg

This program will not work for elements greater than length.

## prodevelopertutorial

That is true, as the code is in C, I used this approach. For dynamic length, you can use C++ with vectors. Logic will remain the same.