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 :
Given an array of integers
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.
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.
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.