The special of this problem is its space limitation

- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.

So, we could turn to Binary Search on values (not the index). I'm still learning this approach. What I could conclude is that:

Suppose there is an unsorted array with `n`

elements, each element is less than `N`

, how could we find the `k`

th smallest element?

We could tweak it to fit finding the duplicate one:

```
def find_duplicate(nums)
left, right = 1, nums.max
while left < right
mid = (left + right)/2
count = nums.count{|x| x <= mid}
if count > mid
right = mid
else
left = mid + 1
end
end
left
end
```

P.S. There is also a `O(n)`

solution. I'm working on it.

*Update*

Oh, I love this problem. The `O(n)`

solution makes use of **Circle Detection** in a perfect way. I've checked several posts in the discussion. Here is my note:

First, we could transfer the problem into a linked list one, as it says

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive)

Then I learnt Floyd's cycle-finding algorithm: Two pointers, `slow`

runs 1 step each time and `fast`

runs 2, would definitely meet if there is a cycle.

Well, they might meet any position in the circle, how would we find the entry point?

What we know

`fast`

has run`a+b+c+b`

steps, and`slow`

with`a+b`

steps`fast`

runs double steps of`slow`

We could conclude that

```
a+b+c+b = 2*(a+b)
# => a == c
```

It means, steps between start point to circle entry equals steps between meet point to circle entry. So when we find the meet point, we could set a new pointer at start position, which would meet `slow`

at the entry point.

Code

```
def find_duplicate(nums)
slow, fast = nums[0], nums[ nums[0] ]
# A loop guaranteed
while slow != fast
slow = nums[slow]
fast = nums[ nums[fast] ]
end
# Set a tag at start point. It would meet slow at the entry of circle.
tag = 0
while tag != slow
tag = nums[tag]
slow = nums[slow]
end
return slow
end
```

Reference: