Find duplicates in an integer array

Given an array of n elements which contains integers from 0 to n-1 only.
The numbers can appear any number of times. Find the repeating numbers.
Example:
Array:  {2, 4, 1, 2, 6, 1, 6, 3, 0}
Output: [1, 2, 6]

Algorithm

Method 1: Naive Solution
Use 2 loops to find duplicates in the array. In outer loop, pick each element one by one and in inner loop check if duplicate exists for that element in the array.
Time Complexity: O(n^2)
Space Complexity: O(1)

Method 2: Use extra space
Since the numbers are in the range 1 to n-1, we can create a count array that will store the count of the numbers in the array.
count[i] represents number of times element i occurs in the array.
In another traversal, find the elements that have count > 1
Time Complexity: O(n)
Space Complexity: O(n)

Method 3:
Traverse the array once and keep reversing the sign of element at array[i]th position.
While traversing, if the sign of array[i]th element is already negative, add it to the duplicates list.
Finally, return duplicates list.
Time Complexity: O(n)
Space Complexity: O(1)

 

Code->

#include <stdio.h>
#include <stdlib.h>

void printRepeating(int arr[], int size)
{
int i;
printf("The repeating elements are: \n");
for (i = 0; i < size; i++)
{
if (arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else
printf(" %d ", abs(arr[i]));
}
}

int main()
{
int arr[] = {1, 2, 3, 1, 3, 6, 6};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*