287. Find the Duplicate Number

287. Find the Duplicate Number (Medium)

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(n²).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Related Topics:
Array, Two Pointers, Binary Search

Similar Questions:

• First Missing Positive (Hard)
• Single Number (Easy)
• Linked List Cycle II (Medium)
• Missing Number (Easy)
• Set Mismatch (Easy)

Solution 1. Binary Search

// OJ: https://leetcode.com/problems/find-the-duplicate-number/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int findDuplicate(vector<int>& A) {
        int L = 1, R = A.size() - 1;
        while (L < R) {
            int M = (L + R) / 2, cnt = 0;
            for (int n : A) cnt += n <= M;
            if (cnt <= M) L = M + 1;
            else R = M;
        }
        return L;
    }
};

Solution 2. Floyd's Tortoise and Hare (Cycle Detection)

// OJ: https://leetcode.com/problems/find-the-duplicate-number/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int findDuplicate(vector<int>& A) {
        int p = A[0], q = A[p];
        for (; p != q; p = A[p], q = A[A[q]]);
        for (p = 0; p != q; p = A[p], q = A[q]);
        return p;
    }
};