Skip to main content

268. Missing Number

easyAsked at Intel

Given an array containing n distinct numbers in [0, n], return the single missing number. Intel reaches for this one because three different optimal solutions exist (XOR, Gauss sum, cyclic placement) — the interviewer is watching which one you reach for and whether you can articulate the tradeoffs.

By Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE phone-screen reports list missing-number as a recurring follow-up to single-number.
  • Levels.fyi (2025-09)— Intel SWE-II interview report cites this with the explicit Gauss-sum follow-up.
  • LeetCode discuss (2025-12)— Intel-tagged in the LC company-frequency filter.

Problem

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

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Examples

Example 1

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

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number.

Example 2

Input
nums = [0,1]
Output
2

Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is missing.

Example 3

Input
nums = [9,6,4,2,3,5,7,0,1]
Output
8

Approaches

1. Sort then scan (brute)

Sort the array. Walk it and return the first index where nums[i] != i. If all match, return n.

Time
O(n log n)
Space
O(1) or O(n) depending on sort
function missingNumberSort(nums) {
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i) return i;
  }
  return nums.length;
}

Tradeoff: Logarithmic-factor slower than the optimal linear options. Use only if you're allowed to mutate the input and want zero scratch space.

2. Gauss sum (optimal — math)

Expected sum is n*(n+1)/2. Subtract the actual sum.

Time
O(n)
Space
O(1)
function missingNumberSum(nums) {
  const n = nums.length;
  const expected = (n * (n + 1)) / 2;
  let actual = 0;
  for (const x of nums) actual += x;
  return expected - actual;
}

Tradeoff: Cleanest one-liner. Risk in C/C++: the sum can overflow for large n. In JS the 2^53 safe-integer range covers n up to ~10^8 so the constraint here (n <= 10^4) is well within safety.

3. XOR (optimal — bit trick)

XOR all indices [0, n] together with every element. Pairs cancel; the missing index survives.

Time
O(n)
Space
O(1)
function missingNumber(nums) {
  let result = nums.length; // start with n; we'll XOR indices [0, n-1] and values
  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }
  return result;
}

Tradeoff: Same asymptotics as Gauss sum but immune to overflow. Intel hardware-SWE rounds prefer XOR because it's overflow-safe by design — relevant when you're working in fixed-width registers.

Intel-specific tips

Intel interviewers will often ask 'can you give me two solutions?' on this problem. The senior signal is naming both Gauss-sum and XOR and stating the tradeoff: Gauss is more intuitive, XOR is overflow-safe. If the interviewer pushes on 'which would you ship in firmware?' — XOR, because fixed-width sum overflows are a real production hazard.

Common mistakes

  • Using a Set/hash — works but is O(n) space, missing the point of the problem.
  • Writing the Gauss formula as n*(n+1)/2 in C/C++ without parenthesizing n+1 first — integer-promotion bugs.
  • In the XOR solution, forgetting to seed with `n` (or equivalently the missing iteration of the index loop).

Follow-up questions

An interviewer at Intel may pivot to one of these next:

  • Find All Numbers Disappeared in an Array (LC 448) — generalize to multiple missing.
  • First Missing Positive (LC 41) — harder: unsorted, can contain negatives, must be O(n) time + O(1) space.
  • What if the array is a stream and you can't see it twice? (XOR works in a single pass; Gauss-sum also works since both are linear and commutative.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Intel prefer XOR over Gauss-sum?

Overflow safety. In a 32-bit C/C++ environment, summing 10^9 values up to INT_MAX overflows the accumulator silently. XOR has no overflow — it's bit-parallel and width-independent.

What if the array could contain duplicates?

Then the problem is ill-defined as stated (more than one number is missing). For the duplicate-and-missing variant (LC 645 Set Mismatch) you XOR and partition by a set bit — the same trick as Single Number III.

Free learning resources

Curated free links for this problem.

More Intel coding interview questions

See all Intel problems →

Companies that also ask Missing Number