Skip to main content

10. Missing Number

easyAsked at Klarna

Find the single missing number from an array containing 0..n.

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

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

  • 1 <= n <= 10^4
  • All values in nums are unique and within [0, n]

Examples

Example 1

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

Example 2

Input
nums = [0,1]
Output
2

Approaches

1. Sort and scan

Sort, then find the first index where nums[i] != i.

Time
O(n log n)
Space
O(1)
function missingNumber(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:

2. Gauss sum

Expected sum is n*(n+1)/2; subtract actual sum to get the missing value. Two passes, constant space, no hashing.

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

Tradeoff:

Klarna-specific tips

Klarna's merchant-settlement reconciliation runs a similar 'expected vs actual' delta against batched payouts; expect a follow-up on overflow safety when the totals exceed 2^53.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →