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.