Skip to main content

268. Missing Number

easyAsked at Bloomberg

An array of n distinct numbers in [0, n] is missing one. Find it. Bloomberg uses this to test whether you know multiple O(n)/O(1) tricks — sum formula AND XOR fold — and can pick between them based on the input constraints.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Bloomberg loops.

  • Glassdoor (2026-Q1)— Bloomberg SWE phone-screen reports cite Missing Number as a follow-up to Single Number.
  • Blind (2025-11)— Bloomberg new-grad reports note the O(1) space constraint as the actual signal.

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. Sum formula (Gauss)

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

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

Tradeoff: Most direct. The closed-form Gauss formula gives the expected sum in O(1). Risk: integer overflow in C++/Java for huge n; safe in JS (64-bit doubles up to 2^53).

2. XOR fold

XOR every index 0..n and every nums[i]. Pairs cancel; the missing index survives.

Time
O(n)
Space
O(1)
function missingNumberXor(nums) {
  let result = nums.length;
  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }
  return result;
}

Tradeoff: No overflow risk. Mention this as the overflow-safe alternative — Bloomberg specifically asks when overflow matters.

Bloomberg-specific tips

Bloomberg interviewers want BOTH formulas verbally. State the sum-formula approach first, then say 'XOR is overflow-safe if integer range is a concern.' That tradeoff awareness is what they grade.

Common mistakes

  • Off-by-one on n — the range is [0, n] (inclusive), so n + 1 distinct values fit, but only n are in the array.
  • Sorting first — O(n log n) when O(n) is possible.
  • Using a hash set — O(n) space when O(1) is achievable.

Follow-up questions

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

  • Find All Numbers Disappeared in an Array (LC 448) — multiple missing.
  • First Missing Positive (LC 41) — find the smallest positive missing.
  • Single Number (LC 136) — same XOR trick.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Sum formula or XOR?

In JS, both work. In a language with 32-bit ints, the sum formula can overflow for huge n. XOR is overflow-safe.

Why initialize result to nums.length, not 0?

Because the loop only covers indices 0..n-1, but the range is 0..n. The missing-from-loop value n is included via the initial value.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →