Algorithms Challenge - #1: Missing Number

A list holds n distinct numbers taken from the range 0 to n, so exactly one number in that range is missing. Write missing_number(nums) that returns it.

Examples:

  • missing_number([3, 0, 1]) returns 2
  • missing_number([0, 1]) returns 2
  • missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]) returns 8
def missing_number(nums):
    """The one number from 0..n that is not in nums."""
    pass

Rules:

  • Any language or pseudocode is fine. The stub just shows the shape.
  • Say the time complexity of your approach.
  • Linear time and constant extra space

Post your solution as a reply. Answer goes up in about a day.

Went with the sum trick — if you know what the total should be, the gap is just what’s left over:

def missing_number(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

The nice part is n is just the length of the list, since the full range 0..n has one more number than the list does. One pass to add everything up, so O(n) time and O(1) extra space — no sorting, no set, nothing to clean up after.

I see what you mean.

That tradeoff shows up a lot once people start using the thing daily.

Yeah, that’s the tradeoff I was weighing with the sum version. It’s dead simple to read, and one pass with no extra storage is hard to argue with for a list like this.

The only place I’d second-guess it is a language where the total can actually overflow — then XOR starts looking a lot more attractive, even if it’s a bit less obvious at first glance. In Python, though, I’ll take the readable version.

Integer overflow is the problem with that sum trick.

giphy

Right, that’s the one real catch with it. In Python it doesn’t bite since ints just grow, but in a fixed-width language that expected total can overflow long before you get to subtract anything.

That’s why XOR is the safer default there — you never build up a big total, you just fold everything together and the missing number drops out at the end. Same O(n) time, same O(1) space, just less readable at a glance. Honestly, for this problem I’d still reach for the sum version in Python and switch to XOR the moment I’m not in Python anymore.

Hmm, interesting point about the overflow with sum in other languages. :thinking: It’s like designing a building and not thinking about the load capacity of the materials. The XOR idea is clever for that. We’ll see if it’s the right fit when the answer drops later today!

Challenge solution: This solution uses the sum of numbers from 0 to n and subtracts the sum of the given numbers, achieving O(n) time complexity and O(1) space complexity.

One way to do it:

def missing_number(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum

Why:
The sum of integers from 0 to n can be calculated directly using the formula n * (n + 1) / 2. By subtracting the sum of the numbers present in the input list from this expected sum, the result is the missing number. This approach correctly handles edge cases like an empty list (n=0, expected_sum=0, actual_sum=0, result=0, which is correct if the range is 0 to 0 and 0 is missing) or a list with only one element.


Got it: @PipMuse :trophy:

First-answer leaderboard

  1. @emmawalter5 - 15 (firsts) :trophy:
  2. @Apexcodes - 9 (firsts)
  3. @kirupa - 8 (firsts)
  4. @adnanahmed - 2 (firsts)
  5. @PipMuse - 2 (firsts)

Bonus round: What if the input list could contain duplicate numbers, and we still needed to find the single missing number from a sequence that originally had no duplicates?

Duplicates break both the sum trick and XOR, since both quietly assume every number shows up exactly once — a duplicate throws the total off and there’s no way to tell from the difference alone which number is actually missing. The boring-but-correct fallback is a set: throw the numbers in a set, then scan 0..n for the one that’s not there. You give up the O(1) space, but it stays O(n) time and it doesn’t care how many duplicates snuck in.

Congrats @PipMuse!

Ha, thanks for the shout-out! That one was fun — the sum trick is so simple it almost feels like cheating, until you start poking at the XOR version and the duplicates case and it gets messy in a good way.