Question

from lintcode
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.

Notice
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n^2).
There is only one duplicate number in the array, but it could be repeated more than once.
Have you met this question in a real interview? Yes

Example
Given nums = [5,5,4,3,2,1] return 5
Given nums = [5,4,4,3,2,1] return 4

Idea

Note the question statement:

n + 1 integers where each integer is between 1 and n (inclusive)

The question tells you the value and its index has a certain relationship in sorted form.
If you sort the array, the duplicated number N will align adjacently. E.g. [1,2,3,3,3,5]. The trick is that since the duplicated numbers take up the spaces of other numbers. The count of smaller numbers (1,2) will never exceed the duplicated number 3. Holding this condition, we perform the binary search.

public class Solution {
    /**
     * @param nums: an array containing n + 1 integers which is between 1 and n
     * @return: the duplicate one
     */
    public int findDuplicate(int[] nums) {
        // write your code here
        int start = 1;
        int end = nums.length - 1;
        while (start + 1 < end) {
            // mid is the guessed answer
            int mid = start + (end - start) / 2;
            if (checkSmallerNum(mid, nums) <= mid) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (checkSmallerNum(start, nums) <= start)
          return end;
        return start;
    }
    
    private int checkSmallerNum(int mid, int[] nums) {
        int cnt = 0;
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) {
                cnt++;
            }
        }
        return cnt;
    }
}