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 run-time complexity should be less than O(n^2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Solution #1:

This solutions uses Pigeonhole principle. For every number in nums, count if num <= mid, if count > mid, there must exist a duplicated number from left -> mid, otherwise the duplicate number is in mid + 1 -> right.

public int findDuplicate(int[] nums) {
    int left  = 1,
        right = nums.length - 1;
    while (left < right) {
        int mid   = left + (right - left) / 2,
            count = 0;
        for (int num : nums) {
            if (num <= mid) {
                count++;
            }
        }
        if (count > mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Solution #2:

Fast slow pointer. Edit later.