# O(N) without extra space & without modifying the array

• ``````//Basically transfer the problem to finding the beginning of cycle in linked list.
public int findDuplicate(int[] nums) {
if(nums.length ==0 )
return 0;
int slow=0, fast=0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
if(slow == nums[slow])
return slow;
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(slow != fast){
if(slow == nums[slow])
return slow;
slow = nums[slow];
fast = nums[fast];
}
return slow;
}``````

• //Can be further simplified.

``````public int findDuplicate(int[] nums) {
if(nums.length ==0 )
return 0;
int slow=0, fast=0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}``````

• for example, [0,1,1,2], what should your code return? you will return 0, but the ans should be 1.

• there will be no 0 in the problem

• genius idea!

• good idea. what we need to find is the node which is the previous node of the node which is the entrance of the ring.

int FindDuplicateNumber::findDuplicateCyclicList(vector<int> &nums) {
if(nums.size() ==0 )
return 0;
int slow =0;
int fast =0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int iDesiredLatter = slow;
while (nums[slow] != iDesiredLatter){
slow = nums[slow];
}
return slow;
}

• good idea. what we need to find is the node which is the previous node of the node which is the entrance of the ring.

• Oh I was wrong. I have to start from original point.

• Oh I was wrong. I have to start from original point.

• simply genius...

• each integer is between 1 and n (inclusive)

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