Missing Number

nums has n elements drawn from the n + 1 values 0..n, so exactly one value is missing. Sorting or hashing solves it, but both cost more than necessary — the missing value can be recovered directly by comparing nums against what a complete 0..n range would look like.

Sorting

Time O(n log n)Space O(1) extra

Sort nums, then walk it looking for the first index where the value does not match the index. If every value matches its index all the way through, the missing number is n (it fell off the end).

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        nums.sort()
        for i, num in enumerate(nums):
            if num != i:
                return i
        return len(nums)

Sorting dominates the cost → O(n log n) time, O(1) extra space if the sort is in-place (ignoring the sort’s own recursion stack).

Expected Sum Minus Actual Sum

Time O(n)Space O(1)

If nothing were missing, nums would contain every value from 0 to n, which sums to n * (n + 1) / 2. Subtracting the actual sum of nums from that expected total leaves exactly the missing value, since every present number cancels out and only the absent one remains.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        expected = n * (n + 1) // 2
        return expected - sum(nums)

Complexity: one pass to sum nums → O(n) time, O(1) space. Correct, but relies on arithmetic (large sums can overflow in fixed-width integer languages, which XOR avoids).

XOR of Indices and Values

OptimalTime O(n)Space O(1)

The same cancellation idea works with XOR instead of addition, and sidesteps any overflow concern. XOR together every index 0..n and every value in nums. Each value that is actually present pairs up with its matching index and cancels to 0 (x ^ x = 0); the one index with no matching value survives.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        result = len(nums)  # accounts for index n, which has no array slot
        for i, num in enumerate(nums):
            result ^= i ^ num
        return result

Tracing nums = [9, 6, 4, 2, 3, 5, 7, 0, 1] (so n = 9, result starts at 9). Each chip tracks the two times its number enters the XOR — once as an index (i) and once as a value (v); when both marks are set, the number cancels to zero:

Numbers 0..9i = used as an indexv = used as a value

Running XOR9result = n = 9

1 / 10

currentcomparingseenresult

Register starts at n = 9, the extra index with no array slot. Each number 0..9 enters the XOR once as an index and once as a value.

Correctness: every present value v at some index gets XORed in twice overall (once as an index somewhere in 0..n, once as the array value) and cancels; the single index in 0..n with no matching array value survives the cancellation and is exactly the missing number.

Complexity: one pass, O(1) work per element → O(n) time, O(1) space — meeting the follow-up exactly, with no risk of integer overflow since XOR never grows the value beyond the input’s bit width.

Sorting

Expected Sum Minus Actual Sum

XOR of Indices and Values

More Bit Manipulation practice