Solution For Find The Duplicate Number

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).

Step by Step Implementation For Find The Duplicate Number

public int findDuplicate(int[] nums) {
        
        // edge case
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        // initialize low and high pointers
        int low = 1;
        int high = nums.length - 1;
        
        // keep iterating until low and high pointers meet
        while (low <= high) {
            
            // find the middle element
            int mid = low + (high - low) / 2;
            
            // initialize a counter to keep track of how many elements are less than or equal to the middle element
            int count = 0;
            
            // iterate through the array and count how many elements are less than or equal to the middle element
            for (int num : nums) {
                if (num <= mid) {
                    count++;
                }
            }
            
            // if the count is greater than the middle element, that means there are duplicate elements in the range [low, mid]
            // so we set high = mid
            if (count > mid) {
                high = mid;
            }
            
            // otherwise, there are duplicate elements in the range [mid + 1, high]
            // so we set low = mid + 1
            else {
                low = mid + 1;
            }
        }
        
        // at this point, low and high pointers have converged and we have found the duplicate element
        return low;
    }

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # initialize a set to store unique elements
        unique_set = set()
        
        # loop through the list
        for num in nums:
            # if the element is already in the set, return it
            if num in unique_set:
                return num
            # otherwise, add it to the set
            unique_set.add(num)

var findDuplicate = function(nums) {
    // create a set to store unique values
    let uniqueValues = new Set();
    
    // iterate through the array
    for (let i = 0; i < nums.length; i++) {
        // if the current value is in the set, return it
        if (uniqueValues.has(nums[i])) {
            return nums[i];
        } else { // otherwise, add it to the set
            uniqueValues.add(nums[i]);
        }
    }
};

class Solution {
public:
    int findDuplicate(vector& nums) {
        int n = nums.size();
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

using System; 

public class Solution {
    public int FindDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];
        
        //Find the intersection point of the two runners.
        do
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);
        
        //Find the "entrance" to the cycle.
        int ptr1 = nums[0];
        int ptr2 = slow;
        while(ptr1 != ptr2)
        {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        
        return ptr1;
    }
}