# O(nlogn) and O(n) solutions in C++, well-explained

• The first solution is quite intuitive which I think it's easy for you guys to understand.

As for the second, the numbers' range is [1...n] while the array is n+1 long which means all the numbers can be the index of the array except for the 0, then let's start from index 0 and follow its number to traverse the array, but soon we'll find out that we cannot leave the array any more (since all the numbers are pointing to index [1...n], then there must be duplicates to form a circle here.

Finding the circle is done, then how about finding the entry of the circle, which is also the duplicate (two numbers pointing to the same index).

There is a classic problem in linked list, we will do it as it does. If you just do not know that, check this post first. Good luck!

``````class Solution {
public:
//Binary search - amazing;
int findDuplicate(vector<int>& nums)
{
int l = 1, h = nums.size()-1;
while(l < h)
{
int count = 0;
int m = (h+l)/2;
for(int i = 0; i < nums.size(); ++i)
if(nums[i]>=l && nums[i]<=m) count++;
if(count <= m-l+1) l = m+1;
else h = m;
}
return l;
}

//similar to find the start of the loop in a linked list;
//the integer is the pointer while the index is the link;
int findDuplicate(vector<int>& nums) {
int slow = nums[0], fast = nums[nums[0]];
while(slow != fast)
{
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(fast != slow)//find the start of the loop which means at least two integer are the same value;
{
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};``````

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