Find The Duplicate Number - Find The Duplicate Number in an Array

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.

Table of Contents

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(n²)

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];
        }
    }
    // Duplicate not found
    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);
        // Check the adjacent elements
        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);
    // Check the adjacent elements
    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];
    }
    // Duplicate not found
    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
            set.add(nums[i]);
        }
        // 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]);
    }
    // Duplicate not found
    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.

Initialize an integer X as XOR of elements from 1 to n, where size of nums array is (n + 1).
Initialize another integer Y as 0.
Traverse the array and update Y as (Y ^ nums[i]), that is, Y stores the XOR of all the elements of nums array.
The duplicate element is (X ^ Y).

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}

Initialize two pointers slow and fast as nums[0].
Do slow = nums[slow] and fast = nums[nums[fast]] while slow and fast are not equal.
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.
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

Reference1 reference2