287. Find the Duplicate Number

Problem:

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.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

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.

Analysis:

6/11/2018 update

Similar approach to linked list cycle II. 

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[0];
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);
        
        int ptr1 = nums[0];
        int ptr2 = slow;
        while(ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        return ptr1;
    }
}

--------------------------------------------------------------------------------------------------------------------------------------------

01/21/2018 update
Below is the version using my current binary search template. Note that the final double check should follow the mid check.

class Solution {
    public int findDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l + 1 < r) {
            int mid = l + (r - l)/2;
            int count = getCount(nums, mid);
            if (count <= mid) r = mid;
            else  l = mid;
        }
        if (getCount(nums, start) <= start) {
            return end;
        }
        return start;

    }

    private int getCount(int[] nums, int mid) {
        int count = 0;
        for (int n: nums) {
            if (n <= mid) count++;
        }
        return count;
    }
}

------------------------------------------------------------------------------------------------------------------------

Problem:

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.
5. 
   

Analysis:
The mid of this problem is not on the array, is on the sequence from 1 to n in ascending order. The sequence 1,2,3,4,4,5. Mid is 3, the count that is less or equal to mid is 3, so that duplicate lies on right. The nums array is just for counting.

Solution:
Double check template is not working here. Because it's possible that duplicate is either start or end, but there is no criteria to filter them out.

However, it's still manageable. By comparing count less and equal to start. if (count <= start) return end otherwise return start. The nature of duplicate enables count (<=) = duplicate number + 1.

class Solution {
    public int findDuplicate(int[] nums) {
        int start= 1, end= nums.length - 1;  
        while (start < end) {  
            int mid = start+ (end- start)/2;  
            int count = 0;
            for (int i: nums) {
                if (i <= mid) count++;
            }
            if (count <= mid) start = mid + 1;
            else end = mid;
         }
        return start;
    }
}