⌘Ctrlk

Pigeonhole

https://binarysearch.com/problems/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) // 2

PreviousLone Integer NextCheck If N and Its Double Exist

Last updated 5 years ago