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 invert the sign of element present at index (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 invert the sign of element present at index (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.

C++

Download   Run Code

Java

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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Andrei Novikov
Guest

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 ‘5’ instead of ‘0’. Moreover it doesn’t work even if we fix the second loop.

Stéphane Moureau
Guest

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

Jerome Labonte
Guest

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

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

Bunny
Guest

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

pankaj
Guest

in approach 1 i believe visited array should be of length greater than the largest element of array

Mridul Ranjan
Guest

This can also be viewed as a finding cycle in a linked list problem – fast and slow turtle method. numbers present at an index represent a cell. Since 0 is not present at any index, index 0 should be taken as the head of the linkedlist. Now, we can apply fast and slow turtle method. Note – I read this solution from LC.

maldi
Guest

the xor solution is wrong.

okay never mind!

Dexter
Guest

What’s the logic behind approach-2? How did we arrive at it ? I’m just a newbie curious to know how to crack these ?

Anshu Goel
Guest

In approach 2 what if absValue-1 is out of index? For example length of the array is 5 but we have an element in it which is 10. In this case if(arr[AbsValue-1]>0) should throw an error.
Is there any logic or concept which I am missing?

Aditya
Guest

As per problem statement, array of length n contains values between 1 & n-1

Anshu Goel
Guest

Ah !! my bad. Thank you !!

James Jayaputera
Guest

In approach 2, why do we need to get an absolute value of an array element? I think the array contains elements between 1 to n-1. Thus, the array element should not be any negative value.

Arafat
Guest

Why do we need to separate loops in xor approach. I think this should work: xor ^= a[i] ^ i;

Arafat
Guest

Full Code:
int xor = 0;
for (int i = 0; i < a.length; i++)
xor ^= a[i] ^ i;
System.out.println(xor);