Given an arraynumscontainingn+ 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.Example 1:Input:`[1,3,4,2,2]`

Output:2Note:1. Youmust notmodify 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 thanO(n^{2}). 4. There is only one duplicate number in the array, but it could be repeated more than once.

## Binary search – O(nlogn)

To prove that at least one duplicate number must exist, we can apply the Pigeonhole principle. Moreover, we can use the principle to find the duplicate. If we focus on `[1..n]`

as our searching space, we can apply binary-search so that in each iteration, we can narrow down by half of the space.

Setting `low=1`

and high=`n`

, we have `mid=(low+high)//2`

. Then we will find `count`

– the number of elements in the `nums`

which are less or equal to `mid`

.

- if
`count > mid`

, according to the Pigeonhole principle, the duplicate must exist in`[1...mid]`

; - if
`count <= mid`

, then there are`n+1-count`

elements in`[mid+1...n]`

, which means there are at least`n+1-mid`

elements in a range of`n-mid`

. Therefore the duplicate must exist in`[mid+1...n]`

.

```
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
n = len(nums)
low = 1
high = n - 1
while low < high:
mid = (low+high)//2
if sum(e <= mid for e in nums) <= mid:
low = mid+1
else:
print(nums)
high = mid
return low
```

## Floyd’s cycle detection – O(n)

@echoxiaolee provides a **brilliant** O(n) approach – if we treat this input as a linked list as shown blow, then **there are at least two nodes linked to the same node** – it becomes a cycle starting point detection problem and we can apply Floyd’s Cycle Detection Algorithm!

Details about the cycle detection are available at Floyd’s Cycle Detection Algorithm so I’d put the code directly:

```
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = nums[0]
fast = nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
fast = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
```