C++ Program to find Duplicate in array
Find Duplicate in Array
Given an array of n elements containing elements from 0 to n-1, with any of these numbers appearing any number of times, find these repeating numbers in O(n) but the challenge is to take only constant memory space.
Explanation: The idea is to use the modulus operator to save the space if we take the mod of a given array with n we would we the same element as every element in the array will be less than n, also if we add n to every element in array we would get the same answer.
eg n =10
3%10 = 3
(3+10)%10 => 3%10 + 10%10 (adding n to array)
#we know that n%n will be 0
Similar if we divide every element in the array with n we would get 0 as an answer since every element is less than n, The approach is to move from left to right and check every element in the array and increase their index value by n.
Example:
n = 4
2 2 3 1
for i = 0 we have 2, so we go to the 2nd index and increase the value by n.
Time Complexity: O(n)
Space Complexity: O(1)
#include <iostream>
using namespace std;
void printRepeating(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
int index = arr[i] % n;
arr[index] += n;
}
for (int i = 0; i < n; i++)
{
if ((arr[i] / n) >= 2)
cout << i << " ";
}
}
// Driver code
int main()
{
int arr[] = { 1, 6, 3, 1, 3, 6, 6 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "The repeating elements are: \n";
// Function call
printRepeating(arr, arr_size);
return 0;
}
Comments