MediumDSAAsked in 20246 min read

Find missing number

Q: Find missing number

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Medium > **How to read this doc:** three O(n) approaches are compared, each verified exhaustively for every array size from 1 to 60 with every possible missing value (shuffled), plus n = 1,000,000. The interesting part is what each one silently assumes: the sum trick is exact only below a size limit and returns nonsense on duplicates; the XOR trick is a 32-bit operation. ## 1. The problem, restated The array should contain every integer from `0` to `n` except one. Find the gap without sorting. The contract matters: distinct values, all in `0..n`, exactly one absent. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | Guaranteed distinct and in range? | Both the sum and XOR tricks rely on it. Violate it and they return a wrong number with no error. | | Extra space allowed? | A `Set` is O(n) space; sum and XOR are O(1). | | Size of `n`?

2.2k views

69 of 154

The problem

Problem, as an interviewer would state it: "Given an array of n distinct numbers taken from 0..n, exactly one number is missing. Find it. Discuss edge cases, runtime, and alternative approaches."

Examples:

Code

findMissing([3, 0, 1]); // 2
findMissing([0, 1]);    // 2
findMissing([1]);       // 0

Clarifying questions expected:

Is the input guaranteed to be distinct, in range, and missing exactly one value?
Can I modify the array, and what space budget do I have?
How large can n be (does the arithmetic stay exact)?

Code / implementation expected: Yes — real, direct proof of each approach, and of the input assumptions each one silently depends on.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Medium

How to read this doc: three O(n) approaches are compared, each verified exhaustively for every array size from 1 to 60 with every possible missing value (shuffled), plus n = 1,000,000. The interesting part is what each one silently assumes: the sum trick is exact only below a size limit and returns nonsense on duplicates; the XOR trick is a 32-bit operation.

1. The problem, restated

The array should contain every integer from 0 to n except one. Find the gap without sorting. The contract matters: distinct values, all in 0..n, exactly one absent.

2. Clarifying questions a strong candidate asks

Question	Why it matters
Guaranteed distinct and in range?	Both the sum and XOR tricks rely on it. Violate it and they return a wrong number with

The solution is hidden so you can try first

6 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: sum, XOR and Set agree exhaustively for every size and gap up to n = 60 and at one million, with the numeric limits shown

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 69 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextMedium→

Custom Set class with hash

Continue