# [leetcode] 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.

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.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Binary search.

low = 1, high = n, mid = (low + high) / 2;

count how many elements are smaller or equal to mid

if this count is bigger than mid, the duplicated number must sits between 1 and mid (inclusive)

else the duplicated number must sits between mid + 1 and high(inclusive)

```// 1 2 2 n = 2
// low = 1, high = 2, mid = 1
// count = 1
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size() - 1;
int low = 1;
int high = n;
while(low != high){
int mid = (low + high) / 2;
int count = 0;
for(int i = 0; i <= n; i++){
if(nums[i] <= mid) count++;
}
if(count > mid){
//duplicated number is between low and mid
high = mid;
}
else{
low = mid + 1;
}
}
return low;
}
};```

Another approach is use fast and slow pointers.

start from index 0, since there are n + 1 numbers all ranges in 0 – n. so a circle must exist. We consider nums[i] as the next node of i. It was like node.next in linked list.

Find the entry of ring in linked list.

```class Solution {
public:
int findDuplicate(vector<int>& nums) {
int fast = 0;
int slow = 0;
fast = nums[nums[fast]];
slow = nums[slow];
while(fast != slow){
fast = nums[nums[fast]];
slow = nums[slow];
}
//fast == slow
fast = 0;
while(fast != slow){
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.