Find a duplicate element in a limited range array

Given a limited range array of size n where array contains elements between 1 to n-1 with one element repeating, find the duplicate number in it.

 

For example,


Input:  { 1, 2, 3, 4, 4 }
Output: The duplicate element is 4
 

Input:  { 1, 2, 3, 4, 2 }
Output: The duplicate element is 2

 


 

Approach 1: (Hashing)

The idea is to use hashing to solve this problem. We can use a visited boolean array to mark if an element is seen before or not. If the element is already encountered before, the visited array will return true.

C++

Download   Run Code


Java

Download   Run Code



Output:

Duplicate element is 4

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 


 

Approach 2:

We can solve this problem in constant space. Since the array contains all distinct elements except one and all elements lies in range 1 to n-1, we can check for duplicate element by marking array elements as negative by using array index as a key. For each array element arr[i], we get absolute value of the element abs(arr[i]) and invert the sign of element present at index abs(arr[i])-1. Finally, we traverse array once again and if a positive number is found at index i, then the duplicate element is i+1.

Above approach takes two traversals of the array. We can achieve the same in only one traversal. For each array element arr[i], we get absolute value of the element abs(arr[i]) and invert the sign of element present at index abs(arr[i])-1 if it is positive else if element is already negative, then it is a duplicate.

C++

Download   Run Code

Java

Download   Run Code



Output:

Duplicate element is 2

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 


 

Approach 3: (using XOR)

We can also solve this problem by taking XOR of all array elements with numbers from 1 to n-1. Since same elements will cancel out each other as a^a = 0, 0^0 = 0 and a^0 = a, we will be left with the duplicate element.

C++

Download   Run Code

Java

Download   Run Code



Output:

Duplicate element is 2

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 


 

Approach 4:

Finally, the post is incomplete without this textbook solution: find sum of all element and find difference between it and all elements which are supposed to be there. Thanks to MiiNiPaa for suggesting this method.

C++

Download   Run Code



Output:

The duplicate element is 4
The duplicate element is 2

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Andrei Novikov
Guest
Andrei Novikov
Solution with XOR (approach 3) is not correct – it uses XOR with N elements at the first loop and with N – 1 elements at the second loop. If you try to process following array { 1, 2, 3, 4, 5 } using this algorithm, then you will see… Read more »
Stéphane Moureau
Guest
Stéphane Moureau

Loop until A[i]+1 is not equal to A[i+1], the duplicate is A[i+1]

Jerome Labonte
Guest
Jerome Labonte

That would only work if the array is sorted, which it does’t have to be. {1,2,3,5,4,2} would return 5 when it should be 2

Michael Keating
Guest
Michael Keating

In approach 4, I believe:
int expected_sum = size * (size - 1) / 2;
should be
int expected_sum = size * (size + 1) / 2;

Bunny
Guest
Bunny

size * (size + 1) / 2 is for 1 to n. The question is for 1 to (n-1).

wpDiscuz