easyDSA

How do you find the missing number in 0..n?

Q: How do you find the missing number in 0..n?

**Intuition.** The set 0..n has a known total ( n(n+1)/2 ). Subtract the actual array sum and the difference is the missing number. An XOR variant achieves the same with no overflow risk. [3,0,1], n=3 → expected sum 6 − actual 4 = 2 0+1+2+3 = 6 3+0+1 = 4</text

871 views

Understand the problem

Explain missing-number approaches.

arraysmath

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Gauss sum + XOR

Run Playground

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

def missing_number_xor(nums):
    result = len(nums)
    for i, x in enumerate(nums):
        result ^= i ^ x
    return result


# --- demo ---
print(missing_number([3, 0, 1]))       # 2
print(missing_number_xor([3, 0, 1]))   # 2

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you find the intersection node of two linked lists?

How do you find the best time to buy and sell a stock?