# O(nlogN) Binary Search and O(n) Circle Detect

• The special of this problem is its space limitation

1. You must not modify the array (assume the array is read only).
2. 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

1. `fast` has run `a+b+c+b` steps, and `slow` with `a+b` steps
2. `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:

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.