# 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:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than O(n2).
- 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;
}
};