Given an array

numscontainingn+ 1 integers where each integer is between 1 andn(inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

- You
must notmodify 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(n`

.^{2})- 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; } };