Find the Duplicate Number

Question

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

Thoughts

The problem is the modification of the array is not allowed. Thus we cannot use hashmap method like searching the missing positive integer in the array. Another problem is the time complexity can only be $$O(1)$$, which doesn't allow us to sort the list easily (Of course we can still do the in-place sorting).

A simple idea is that we need to do the calculation with the items in the array and utilize the constant space to store the data which can help us to search the duplicated number.

Considering the characteristics of the array. We can use the index which is compatible to the value of the item in the array to do the calculation to find the duplicated number.

Code

Reference: https://discuss.leetcode.com/topic/36801/python-solution-with-o-1-space-and-o-nlogn-time

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low = 0
        high = len(nums) - 1
        mid = (high + low) / 2
        while low < high - 1:
            mid = (high + low) / 2
            count = 0
            for num in nums:
                if mid < num <= high:
                    count += 1
            if count > high - mid:
                low = mid
            else:
                high = mid
        return high