Find The Duplicate Number - Leetcode Solution

The problem "Find The Duplicate Number" on LeetCode asks us to find the duplicate number in an array of n+1 integers where each integer is between 1 and n (inclusive).

The naive solution to this problem would be to use a nested loop and compare each element with every other element in the array. For an array of size n+1, this solution would have a time complexity of O(n^2). However, this solution is not practical for larger arrays.

A better solution is to use the pigeonhole principle and binary search. We know that there are n integers between 1 and n (inclusive), so at least one integer must be repeated. We can divide the array into two halves, with one half containing the numbers 1 to n/2 and the other half containing the numbers n/2 + 1 to n.

If the number of integers in the first half of the array is greater than n/2, then there must be a duplicate in that half of the array. Otherwise, there must be a duplicate in the second half of the array. We can repeat this process recursively until we find the duplicate.

To implement this solution, we can use a modified binary search algorithm. Initially, we set the lower and upper bounds to 1 and n, respectively. We then calculate the mid-point of the bounds. We count the number of integers in the array that are less than or equal to the mid-point value. If the number of integers is greater than the mid-point value (i.e. there are more integers in the first half of the array), we set the upper bound to the mid-point value. Otherwise, we set the lower bound to the mid-point value + 1. We repeat this process until we find the duplicate.

Here is the Python code implementation of the above algorithm:

def findDuplicate(nums): """ :type nums: List[int] :rtype: int """ n = len(nums) - 1 left, right = 1, n while left < right: mid = (left + right) // 2 count = sum(num <= mid for num in nums) if count > mid: right = mid else: left = mid + 1 return left

The time complexity of this algorithm is O(n log n) and the space complexity is O(1).

1