# 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

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

Example 2:

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

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(n2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

# Solution

Approach 1: Binary search - O(nlogn).

Approach 2: Cycle - O(n). Jump to an element based on the index. There must be one cycle.

# Code (Python)

Approach 1:

    def findDuplicate(self, nums):
        # O(NlogN) idea: binary search for answer. Try n/2, and if nums <= n/2 is greater than n/2, then answer within [1, n/2]
        lo, hi = 1, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if sum([1 if num <= mid else 0 for num in nums]) > mid:
                hi = mid
            else:
                lo = mid + 1
        return lo

Approach 2:

    def findDuplicate(self, nums: List[int]) -> int:
        # O(N) idea
        # each item points to the address of the next item in the linked list
        # a duplicate means there are 2+ items pointing to the same node -> a cycle
        fast, slow = nums[0], nums[0]
        fast = nums[nums[fast]]
        slow = nums[slow]
        while fast != slow:
            fast = nums[nums[fast]]
            slow = nums[slow]
        dup = nums[0]
        while dup != slow:
            slow = nums[slow]
            dup = nums[dup]
        
        return dup

# Code (C++)

Approach 1:

// Binary search - O(nlogn)
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int lo = 1;
        int hi = n;
        while (lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            for (int i = 0; i < n; ++i)
            {
                if (nums[i] < mid)
                    count++;
            }
            if (count >= mid)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return lo - 1;
    }
};

Approach 2:

// Cycle - O(n).
// nums[0] must not be 0. As there are duplicates, there must be elemnts
// containing the same value, that is, pointing to the same index. So
// there must be cycle.
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        while (slow != fast);
        fast = 0;
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};