Find the Duplicate Number

Problem: Given an array of integers containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one duplicate number in the given array, return this duplicate number.

Example:

Input: nums = [3, 1, 3, 4, 2, 3]
Output: 3

Approach: Please note that the duplicate number can appear any number (> 1) of times so if you are thinking of XOR approach, just stop there. Now see what are the other obvious approaches:

1. Sorting - Will work but the Time complexity will be O(nlogn)
2. Hash - Will work and solve the problem in O(n) only but will take the space at least O(n).

Both the above approaches can solve this and the complexities are not bad but can we do better? 

Let's look at the problem differently. If you see there is a cycle here because of duplicate number. Just like linked list If I defined node -> next as array[currentValue] then if you traverse in this way, you will see there is a cycle exist in the input array itself. Lets take the above example:

• currNum = array[0] = 3
• currNum = array[currNum] = array[3] = 4
• currNum = array[currNum] = array[4] = 2
• currNum = array[currNum] = array[2] = 3 (This is the starting point of  cycle)

Now we can use the same approach which we used in finding loop in Linked List to solve this problem. Here is the basic of this algorithm:

• slow = array[slow]
• fast = array[array[fast]]

That's all!

Implementation in C#:

    public int FindDuplicate(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return -1;

        }

        int slow = nums[0], fast = nums[0];

        do {

            slow = nums[slow];

            fast = nums[nums[fast]];

        } while (slow != fast);

        slow = nums[0];

        while(slow != fast)

        {

            slow = nums[slow];

            fast = nums[fast];

        }

        return slow;

    }

Complexity: O(n)