Find the Duplicate Number Leetcode Solution

Hello coders, Today I am going to solve another Leetcode problem titled ” Find the Duplicate Number Leetcode Solution “. As we know any number which appears more than once is known as a duplicate number.

Let’s see the complete problem statement :

Problem statement:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2
Explanation: Here, we can clearly see 2 appears two times. Hence the output will be 2.

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3
Explanation: Here, 3 appears two times and the output will be 3.

Find the Duplicate Number Leetcode Solution in Python

#Find the Duplicate Number Leetcode Solution in Python

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        
        low = 1
        high = len(nums) - 1
        
        while low <= high:
            cur = (low + high) // 2
            count = 0

            # Count how many numbers are less than or equal to 'cur'
            count = sum(num <= cur for num in nums)
            if count > cur:
                dup = cur
                high = cur - 1
            else:
                low = cur + 1
                
        return dup
    
        #Find the Duplicate Number Leetcode Solution in Python

Disclaimer: This problem(Find the Duplicate Number Leetcode solution) is originally created by LeetcodeCodesagar only provides a solution for it. This solution is only for Educational and learning purposes.

Leave a Comment