287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify 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 than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Solution:

Since nums array contains 1 to n, nums[0] must between 1 and n. Assume there is no duplicate in this array, nums[nums[0]] must !=nums[0] and any subsequent nums[x] must be a distinct number from 1 to n.

However there  must exist at least one duplicate because, n+1 > length(1 to n) . 

So when we keep nums(n)=nums[nums(n-1)], we will fall into a cycle because there must exsit a distinct index m and n to make nums[m]==nums[n] which is the duplicate number we are trying to find here.

So the whole problem becomes a cycle detecting problem. 

And we know there is a great algorithm that can find the entry point of the cycle: 

142. Linked List Cycle II Leetcode Java

Similarly here, we use the same technique, walker and runner to find the entry point.
Time complexity: O(n)

  public int findDuplicate(int[] nums) {  
     int walker=nums[0];  
     int runner=nums[0];  
     do{  
       walker=nums[walker];  
       runner=nums[nums[runner]];  
     }while(walker!=runner);  
     walker=nums[0];  
     while(walker!=runner){  
       walker=nums[walker];  
       runner=nums[runner];  
     }  
     return walker;  
   }  

Another O(nlg(n)) solution:
Normal binary search usually search the index while target is the element of the array. But this one is opposite and we search number itself.
We set initial l=1 and r=n,
Eg.n=6, so the array may be 1,2,3,4,5,6 + a duplicate number
m is 3, so if duplicate is <=3, which means if we count all the element that is <=3, the count must > 3
if duplicate is >3, the count must <=3.
So according the count, we can either cut the left half or right half.
While counting takes O(n), so the total time complexity is O(nlgn).

 public int findDuplicate(int[] nums) {  
     int l=1;  
     int r=nums.length-1;  
     while(l<r){  
       int m=(r-l)/2+l;  
       int count=0;  
       for(int i=0;i<nums.length;i++){  
         if(nums[i]<=m) count++;  
       }  
       if(count>m) r=m;  
       else l=m+1;  
     }  
     return l;  
   }