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 Alex Chen, 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.

Practice these live with InterviewChamp.AI

Drill Missing Number and other Intel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →