# 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.

## Java

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.

## Java

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.

## Java

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.

## Java

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).

(3 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

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

Guest
Stéphane Moureau

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

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

Guest
Michael Keating

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

Guest

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

Guest

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

Guest
Mridul Ranjan

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.

Guest

the xor solution is wrong.

okay never mind!

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 ?

Guest
Anshu Goel

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?

Guest

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

Guest
Anshu Goel

Ah !! my bad. Thank you !!

Guest
James Jayaputera

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.

Guest

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

Guest

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