Skip to main content

8. Missing Number

easyAsked at Revolut

Find the one number missing from a permutation of 0..n, a Revolut warm-up that mirrors finding a gap in a sequence of FX trade IDs.

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. Solve it with O(1) extra space if possible.

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • All numbers are unique

Examples

Example 1

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

Example 2

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

Approaches

1. Hash set lookup

Put nums in a set then scan 0..n.

Time
O(n)
Space
O(n)
const s = new Set(nums);
for (let i=0;i<=nums.length;i++) if (!s.has(i)) return i;

Tradeoff:

2. Sum or XOR

Use n*(n+1)/2 minus the array sum, or XOR indices and values. Constant space.

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

Tradeoff:

Revolut-specific tips

Revolut prefers the XOR variant over the Gauss sum because it dodges 32-bit overflow on huge ID ranges — call that out as a financial-precision habit.

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 Revolut interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →