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 Leetcode. Codesagar only provides a solution for it. This solution is only for Educational and learning purposes.