287

287. Find the Duplicate Number (Medium)

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

 

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

Companies: Amazon, Adobe, Yahoo, Microsoft, PhonePe, Goldman Sachs, Apple, Google, Facebook, Uber, Bloomberg, Qualcomm, Cisco, Walmart Labs

Related Topics:
Array, Two Pointers, Binary Search, Bit Manipulation

Similar Questions:

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

Solution 1. Binary Search

Numbers less than the duplicate number must have frequencies less than or equal to themselves.

Examples:

• A = [1 2 3 3 4], 1,2 have frequencies (1,2) less than or equal to themselves.
• A = [3 2 3 3 4], 1,2 have frequencies (0,1) less than or equal to themselves.

L < R template:

• Range: [1, A.size()-1]
• Let cnt be the count of numbers less than or equal to M. If cnt <= M, the duplicate number is greater than M, so L = M + 1; otherwise, R = M.

// 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;
    }
};

L <= R template:

• Range: [1, A.size()-1].
• Let cnt be the count of numbers less than or equal to M. The answer is the first number that cnt > itself. So, we return L in the end.

// 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 - 1;
        }
        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;
    }
};

Solution 3. Cycle Sort

// 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) {
        for (int i = 0, N = A.size(); i < N; ++i) {
            while (A[i] - 1 != i) {
                if (A[i] == A[A[i] - 1]) return A[i];
                swap(A[i], A[A[i] - 1]);
            }
        }
        return -1;
    }
};