package miscellaneous.math.statistics.lc287_findtheduplicatenumber;

/**
 * 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:
 *  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(n2).
 *  There is only one duplicate number in the array, but it could be repeated more than once.
 */
public class Solution {

    // eg.[1,3,4,2,2]
    // mid = 2, count = 3 -> high = mid-1 = 1
    // mid = 1, count = 4 -> low = mid+1 = 2
    public int findDuplicate(int[] nums) {
        // Numbers in nums[N] are all in [1,N-1]
        int low = 1, high = nums.length - 1;

        // Note that low,mid,high have nothing with nums array
        // nums array only provides statistics info to locate that dup
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int count = 0;
            for (int num : nums) {
                if (num <= mid) {
                    count++;
                }
            }

            // #num <= mid should =mid if no dup. eg.[1,2,3,4,5], mid=3
            // With dup=1, [1,1,2,3,4], count=3 > mid=2. means one smaller dup exists
            if (count > mid) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

}

@@ -601,16 +601,938 @@
 tion %7B%0A%0A
+    // Nice use of binary search in O(NlogN) time.%0A    public int findDuplicate(int%5B%5D nums) %7B%0A        int l = 1, r = nums.length; /* search in range number %5B1,n%5D not actual nums array */%0A        while (l %3C r) %7B%0A            int m = l + (r - l) / 2;%0A            int cnt = 0;%0A            for (int n : nums) %7B%0A                if (n %3C= m) cnt++;%0A            %7D%0A            if (cnt %3C= m) l = m + 1;/* cnt%3C=m: all distinct or miss some in %5B1,m%5D caused by duplicates in %5Bm,n%5D */%0A            else r = m;             /* cnt%3Em:  duplicates in %5B1,m%5D */%0A        %7D%0A        return l;%0A    %7D%0A%0A    public int findDuplicate3(int%5B%5D nums) %7B%0A        int slow = 0, fast = 0;%0A        do %7B%0A            slow = nums%5Bslow%5D;%0A            fast = nums%5Bnums%5Bfast%5D%5D;%0A        %7D while (slow != fast);%0A%0A        int slow2 = 0;%0A        while (slow != slow2) %7B%0A            slow = nums%5Bslow%5D;%0A            slow2 = nums%5Bslow2%5D;%0A        %7D%0A        return slow;%0A    %7D%0A%0A
     // e
@@ -1656,32 +1656,33 @@
 nt findDuplicate
+1
 (int%5B%5D nums) %7B%0A 

find the duplicate number