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 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.
Binary search – O(nlogn)
To prove that at least one duplicate number must exist, we can apply the Pigeonhole principle. Moreover, we can use the principle to find the duplicate. If we focus on
[1..n] as our searching space, we can apply binary-search so that in each iteration, we can narrow down by half of the space.
low=1 and high=
n, we have
mid=(low+high)//2. Then we will find
count – the number of elements in the
nums which are less or equal to
count > mid, according to the Pigeonhole principle, the duplicate must exist in
count <= mid, then there are
[mid+1...n], which means there are at least
n+1-midelements in a range of
n-mid. Therefore the duplicate must exist in
class Solution: def findDuplicate(self, nums: List[int]) -> int: n = len(nums) low = 1 high = n - 1 while low < high: mid = (low+high)//2 if sum(e <= mid for e in nums) <= mid: low = mid+1 else: print(nums) high = mid return low
Floyd’s cycle detection – O(n)
@echoxiaolee provides a brilliant O(n) approach – if we treat this input as a linked list as shown blow, then there are at least two nodes linked to the same node – it becomes a cycle starting point detection problem and we can apply Floyd’s Cycle Detection Algorithm!
Details about the cycle detection are available at Floyd’s Cycle Detection Algorithm so I’d put the code directly:
class Solution: def findDuplicate(self, nums: List[int]) -> int: slow = nums fast = nums[nums] while slow != fast: slow = nums[slow] fast = nums[nums[fast]] fast = 0 while slow != fast: slow = nums[slow] fast = nums[fast] return slow