Missing Number

mosesg1123
Apr 28
3 min read

When you need to find the one missing entry in a sequence—say missing log IDs, seats, or data packets—Missing Number is the classic warm-up. It tests your ability to exploit mathematical properties and bit tricks for O(n) time and O(1) space.

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], find the one number in that range that is missing from nums. Return that missing number.

Input: nums = [3,0,1]
Output: 2

1. Clarify Requirements Before Jumping Into Code

Let me check the details:

Array length is n, values distinct, drawn from 0 through n inclusive.
Exactly one value in that full range is missing.
We need to return that missing integer.
Target time complexity is O(n) and extra space O(1) if possible.
Can I modify nums? Prefer not, but it’s allowed for in-place tricks.

2. Identify the Category of the Question

This is an array + bit/maths trick problem. Common patterns include:

Summation / mathematical formulas (sum of 0…n = n(n+1)/2)
XOR-based cancellation (a ⊕ a = 0)
Hashing (store seen numbers)
In-place swap / cyclic sort (put each number to its index)

Recognizing “one missing from 0…n” often points to sum or XOR solutions.

3. Consider a Brute-Force Approach to Understand the Problem

Brute-force: for each i from 0 to n, scan nums to see if i is present. If not, return i.

Time Complexity: O(n²)
Space Complexity: O(1)
Drawback: Quadratic time too slow for large n

4. Brainstorm More Solutions

I need O(n) time. A hash set would let me check presence in O(1): build a set of all nums, then loop i from 0 to n, return the first i not in the set. That’s O(n) time and O(n) extra space.

Can I do it in O(1) extra space? Two classic tricks come to mind:

Summation formula: Sum of all numbers 0 + 1 + … + n equals n(n+1)/2. If I subtract the sum of the array from that total, the difference is the missing number. That’s O(n) time, O(1) space. I need to be mindful of integer overflow in languages like Java, but in Python it’s safe.
XOR cancellation: If I XOR all indices 0 through n and XOR all elements in nums, pairs cancel, leaving the missing number. Also O(n) time, O(1) space.

Which would I choose on the fly? The summation trick is the first one I recall—just write the arithmetic formula. If I worry about overflow, I’d switch to XOR, which avoids large sums.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Hash Set	O(n)	O(n)	Straightforward	Uses extra memory
Summation Formula	O(n)	O(1)	Very simple arithmetic	Potential overflow in some languages
XOR Cancellation	O(n)	O(1)	No risk of overflow, pure bitwise	Slightly less intuitive

Summation is easy; XOR is equally O(1) space but avoids overflow concerns.

6. Write Pseudocode to Structure Your Thoughts

function missingNumber(nums):
  n = length(nums)
  expectedSum = n * (n + 1) / 2
  actualSum = 0
  for x in nums:
    actualSum += x
  return expectedSum - actualSum

7. Consider Edge Cases

Smallest array: nums = [0], then n=1, expected sum=1, actual=0 → returns 1.
Missing 0: nums = [1,2,3], expected sum=6, actual=6 → returns 0.
Missing n: nums = [0,1,2], expected sum=6, actual=3 → returns 3.
Large n: array up to millions—algorithm still linear.
Unordered input: works regardless of order.

8. Write Full Code Syntax

def missingNumber(nums):
    n = len(nums)
    # Use integer arithmetic for expected sum
    expected = n * (n + 1) // 2
    actual = 0
    for x in nums:
        actual += x
    return expected - actual

9. Test Your Code

assert missingNumber([3,0,1]) == 2
assert missingNumber([0,1]) == 2
assert missingNumber([1,2]) == 0
assert missingNumber([0]) == 1
assert missingNumber([1]) == 0
print("All tests passed!")

10. Key Lessons to Remember for Future Questions

Look for mathematical identities (sum, product) when the problem involves complete ranges. Remember these formulas:
The XOR trick shines when you have pairs of identical values that cancel each other out—because x ⊕ x = 0 and x ⊕ 0 = x. Spot it in problems where everything should appear twice except one unique element (or two unique elements), or when you need to combine two sequences and isolate differences. Whenever the task reduces to “everything paired except this,” XOR often gives you a neat linear-time, constant-space solution.

Good Luck and Happy Coding!