Home Â» Technical Interview Questions Â» Array Interview Questions Â» Find The Duplicate Number

# Find The Duplicate Number

Given an array nums containing (n + 1) elements and every element is between 1 to n. If there is only one duplicate element, find the duplicate number.

## Examples

Input:
nums = {1, 3, 4, 2, 2}
Output:
2

Input:
nums = {3, 1, 3, 4, 2}
Output:
3

## Naive Approach for Find The Duplicate Number

### Method 1 (Brute Force)

Traverse the array from index 0 and for every element check if it repeated in the array elements ahead of it.
If it is repeated, then this is the duplicate element, else continue for the next element.
Time Complexity = O(n2)

#### JAVA Code

```public class FindTheDuplicateElement {
private static int findDuplicate(int nums[]) {
int n = nums.length;

for (int i = 0; i < n; i++) {
// For every element check if it is repeated in the elements ahead of it
for (int j = i + 1; j < n; j++) {
// If repeated, this is the duplicate element
if (nums[j] == nums[i])
return nums[i];
}
}
// No duplicate found
return -1;
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 2, 2};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 3, 4, 2};
System.out.println(findDuplicate(nums));
}
}```

#### C++ Code

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
for (int i = 0; i < n; i++) {
// For every element check if it is repeated in the elements ahead of it
for (int j = i + 1; j < n; j++) {
// If repeated, this is the duplicate element
if (nums[i] == nums[j])
return nums[i];
}
}
return -1;
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 2, 2};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 3, 4, 2};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```2
3```

### Method 2 (Sorting)

Sort the array in ascending order, the duplicate elements will come adjacent to each other.
Traverse the sorted array and return the duplicate element.
Time Complexity = O(n log(n))

#### JAVA Code

```import java. util. Arrays;
public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
// Sort the array
Arrays.sort(nums);
for (int i = 0; i < n - 1; i++) {
// If adjacent elements are equal, this is the duplicate element
if (nums[i] == nums[i + 1])
return nums[i];
}
// No duplicate found
return -1;
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 2, 2};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 3, 4, 2};
System.out.println(findDuplicate(nums));
}
}```

#### C++ Code

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
// Sort the array
sort(nums, nums + n);
for (int i = 0; i < n - 1; i++) {
// If adjacent elements are equal, this is the duplicate element
if (nums[i] == nums[i + 1])
return nums[i];
}
return -1;
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 2, 2};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 3, 4, 2};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```2
3```

## Optimal Approach for Find The Duplicate Number

### Method 1 (Hashing)

Create a HashSet and for every element of nums array, if the current element is present in the HashSet then it is the duplicate else insert the element into the HashSet.
Time Complexity = O(n)
Space Complexity = O(n)

#### JAVA Code for Find The Duplicate Number

```import java.util.*;
public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
// Create a HashSet
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
// If the HashSet contains the element, then this is the duplicate
if (set.contains(nums[i]))
return nums[i];
// Else add the element to the set
}
// No duplicate found
return -1;
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 1, 2, 5};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 4, 2, 5, 5};
System.out.println(findDuplicate(nums));
}
}```

#### C++ Code for Find The Duplicate Number

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
// Create a HashSet
unordered_set<int> set;
for (int i = 0; i < n; i++) {
// If the HashSet contains the element, then this is the duplicate
if (set.find(nums[i]) != set.end())
return nums[i];
// Else add the element to the set
set.insert(nums[i]);
}
return -1;
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 1, 2, 5};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 5, 4, 2, 5};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```1
5```

### Method 2 (XOR)

According to XOR property (X ^ X) = 0, this property can be used to solve the above problem.

1. Initialize an integer X as XOR of elements from 1 to n, where size of nums array is (n + 1).
2. Initialize another integer Y as 0.
3. Traverse the array and update Y as (Y ^ nums[i]), that is, Y stores the XOR of all the elements of nums array.
4. The duplicate element is (X ^ Y).
READ  Check in binary array the number represented by a subarray is odd or even

Time Complexity = O(n),Â with two traversals one for building X and one for Y
Space Complexity = O(1)

#### JAVA Code for Find The Duplicate Number

```public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
// Initialise X as XOR of elements from 1 to n
// Size of nums is (n + 1), here represented as n
int X = 0;
for (int i = 1; i <= n - 1; i++)
X = (X ^ i);

// Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
int Y = 0;
for (int i = 0; i < n; i++) {
Y = Y ^ nums[i];
}

// Duplicate element is (X ^ Y)
return (X ^ Y);
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 2, 4};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 3, 4, 2};
System.out.println(findDuplicate(nums));
}
}```

#### C++ Code for Find The Duplicate Number

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
// Initialise X as XOR of elements from 1 to n
// Size of nums is (n + 1), here represented as n
int X = 0;
for (int i = 1; i <= n - 1; i++)
X = X ^ i;

// Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
int Y = 0;
for (int i = 0; i < n; i++)
Y = Y ^ nums[i];

// Duplicate element is (X ^ Y)
return (X ^ Y);
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 2, 4};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 3, 4, 2};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```4
3```

### Method 3 (Cycle Detection)

The above problem can be solved by the cycle finding algorithm in Linked List using two pointers slow and fast, the slow pointer moves by one step and fast move by two steps in every iteration.

Consider the example,
nums[] = {1, 3, 4, 2, 2}

1. Initialize two pointers slow and fast as nums[0].
2. Do slow = nums[slow] and fast = nums[nums[fast]] while slow and fast are not equal.
3. After step 2, assign slow as nums[0] and move slow and fast pointer one step each, that is,
slow = nums[slow]
fast = nums[fast]
while slow and fast are not equal.
4. After step 3, both slow and fast points to the duplicate element.

Time Complexity =Â O(n)
Space Complexity = O(1)

#### JAVA Code for Find The Duplicate Number

```public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
//Initialize two pointers slow and fast as nums[0].
int slow = nums[0], fast = nums[0];
// Do slow = nums[slow] and fast = nums[nums[fast]]
// while slow and fast are not equal.
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);

// assign slow as nums[0]
slow = nums[0];
// Move slow and fast by one step each while slow and fast are not equal
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

// Both slow and fast points to the duplicate element
return fast;
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 4, 2};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 5, 4, 2, 5};
System.out.println(findDuplicate(nums));
}
}```

#### C++ Code for Find The Duplicate Number

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
//Initialize two pointers slow and fast as nums[0].
int slow = nums[0], fast = nums[0];
// Do slow = nums[slow] and fast = nums[nums[fast]]
// while slow and fast are not equal.
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);

// assign slow as nums[0]
slow = nums[0];
// Move slow and fast by one step each while slow and fast are not equal
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

// Both slow and fast points to the duplicate element
return fast;
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 4, 2};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 5, 4, 2, 5};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```4
5```
 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions