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; }