178 — Missing Number

178 — Missing Number

LeetCode 268 · Easy. Given an array nums containing n distinct numbers taken from the range 0 to n inclusive, return the one number in that range that is missing from the array.

---

🍽️ Intuition

If you know the complete guest list should be 0 through n, and you're handed a stack of check-in slips for everyone who actually showed up, the missing guest is whoever's name never got called off the list. The direct way to find them: write every expected name on a whiteboard, cross one off every time you see a matching check-in slip, and whoever's left uncrossed at the end is your answer — that's exactly what a Set of 0...n with removals gives you. But there's a trick that skips the whiteboard entirely: XOR every index 0 to n-1, every value in nums, and n itself, all together. Every number that's actually present in the array gets XOR'd twice — once as an index, once as a value — and cancels itself out to 0, leaving only the one number that never had a matching index to pair with.

nums = [3, 0, 1]     (n = 3, expected range 0...3)

indices:        0    1    2
values:         3    0    1
plus n:                        3

XOR everything together:
0 ^ 1 ^ 2 ^ 3 ^ 0 ^ 1 ^ 3
= (0^0) ^ (1^1) ^ (3^3) ^ 2
=   0   ^   0   ^   0   ^ 2
= 2                              <- the missing number

---

🚩 Pattern-Recognition Cue

"n distinct numbers from a known range, exactly one missing" is the cue for an XOR-pairing trick: whenever every value except one has a natural counterpart it should cancel against (here, each present value cancels against the index it could have occupied), XOR-ing the full expected set against the actual set isolates the unpaired survivor without ever storing which numbers were seen.

---

🐢 Brute Force

Put every number from 0 to n into a Set, then remove every number that actually appears in nums. Whatever's left in the set is the missing number.

func missingNumberBruteForce(_ nums: [Int]) -> Int {
    let n = nums.count
    var expected = Set(0...n)

    for num in nums {
        expected.remove(num)
    }

    return expected.first ?? -1   // unreachable given the problem's guarantee
}

// smoke test
print(missingNumberBruteForce([3, 0, 1]))          // 2
print(missingNumberBruteForce([0, 1]))             // 2
print(missingNumberBruteForce([9, 6, 4, 2, 3, 5, 7, 0, 1]))   // 8

Big-O: O(n) time — building the set and removing n elements are each O(n) on average. O(n) extra space for the set holding up to n + 1 numbers.

---

🚀 Optimal

XOR every index from 0 to n - 1, every value in nums, and n itself, all into one running result. Every present number cancels against the index it lines up with, leaving only the missing one.

func missingNumber(_ nums: [Int]) -> Int {
    var result = nums.count   // start with n already folded in

    for (i, num) in nums.enumerated() {
        result ^= i
        result ^= num
    }

    return result
}

// smoke test — same cases as the brute force
print(missingNumber([3, 0, 1]))          // 2
print(missingNumber([0, 1]))             // 2
print(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]))   // 8

Big-O: O(n) time — one pass, two XORs per element. O(1) extra space — just the running accumulator, no set required.

---

🔑 The Key Insight

The brute force's Set exists to answer "which numbers from 0...n did I never see?" by physically removing everything it did see. XOR answers the same question without ever storing the "seen" state: because every value that's actually present in nums gets XOR'd in twice — once implicitly as an index position, once explicitly as a value — those pairs cancel to 0 regardless of what order they arrive in. Only the one number with no index to pair against survives the cancellation, which is precisely the missing number.

---

🔗 Related Chapters

• Hash Maps and Hash Sets — the Set of expected values the brute force builds and prunes down to the missing number.
• Bit Manipulation Tricks — the XOR-pairing trick (indices against values) that isolates the one unpaired number in the optimal solution.

---

🧸 Memory Sentence

Missing Number is a guest list with one no-show — XOR every index against every value and n, and only the one name with no check-in slip survives the cancellation.

---

✅ Check Your Understanding

1. Why does the optimal solution seed result with nums.count (n) before the loop even starts, rather than only XOR-ing indices and values?
2. Walk through missingNumber([0, 1]) step by step — which index/value pairs cancel, and which number is left over?
3. Why must nums's values and the loop's indices both range only up to n - 1 (with n handled separately) for the cancellation to work out to exactly one leftover number?
4. The brute-force Set approach and the XOR approach both run in O(n) time. What's the concrete cost difference between them that makes the XOR version preferable when extra memory is scarce?

---

⬅️ Previous: Reverse Bits · Next: Sum of Two Integers ➡️