Find the missing number
An array contains distinct values from 0 through n with one value missing. Find the missing value.
Course progress
Problem 31 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
numbers = [3, 0, 1]
Expected output
2
What is happening?
The values should contain every integer from 0 through 3. Comparing that range with the input reveals that 2 is absent.
Solution strategy
Build the right mental model
XOR every expected index and every actual value. Equal values cancel, leaving only the missing number without risking arithmetic overflow.
Core concepts
XOR · arrays
Complexity
Time O(n), space O(1).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for missing-number
using System;
class Program
{
static int FindMissing(int[] numbers)
{
int missing = numbers.Length;
for (int i = 0; i < numbers.Length; i++) missing ^= i ^ numbers[i];
return missing;
}
static void Main()
{
Console.WriteLine(FindMissing(new[] { 3, 0, 1 }));
}
}Knowledge check
Questions students often ask
What is the main idea behind find the missing number?
XOR every expected index and every actual value. Equal values cancel, leaving only the missing number without risking arithmetic overflow.
What is the time and space complexity of this solution?
Time O(n), space O(1).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.