Pigeonhole
You are given a list nums of length n + 1 picked from the range 1, 2, ..., n. By the pigeonhole principle, there must be a duplicate. Find and return it. There is guaranteed to be exactly one duplicate.
Bonus: Can you do this in linear time and constant space?
This solution uses the formula for the sum of numbers from 1 to n. Then the duplicate number is the number left over subtracting that sum, which we will call the expected sum, from the actual sum of all numbers in the list.
From here.
class Solution:
def solve(self, nums):
n = len(nums) - 1
return sum(nums) - n * (n + 1) // 2Last updated
Was this helpful?