Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Find the Missing Number

Find the missing value from 1 through n using XOR without overflow.

EasyArraysPattern: array traversal, xor

Problem statement

An array contains n - 1 distinct numbers from 1 through n. Return the missing number.

For n = 5 and [1, 2, 4, 5], the answer is 3.

Constraints & requirements

INPUT
Distinct values from 1 through n
MISSING
Exactly one range value
TARGET
Linear time and constant space

Examples 3 test cases

  1. Example 1 Middle missing

    Input
    [1, 2, 4, 5], n = 5
    Output
    3

    Checks cancellation in the middle.

  2. Example 2 First missing

    Input
    [2, 3], n = 3
    Output
    1

    Checks the lower boundary.

  3. Example 3 Last missing

    Input
    [1, 2, 3], n = 4
    Output
    4

    Checks the upper boundary.

Hints Optional

Hints become more specific one step at a time.
01Look for cancellation

For any integer x, x XOR x becomes 0 and x XOR 0 remains x.

02Include both sets of values

XOR every expected number from 1 through n and every value present in the array.

03Use the indexes

Start answer at n, then XOR index + 1 and values[index] in the same loop.

How to think before coding

The input promises distinct values from 1 through n, with exactly one absent. Start from the slow presence check, then look for cancellation rather than a data structure: every present value appears once in the expected range and once in the input. XOR removes those pairs. Include n separately because the n−1 array positions supply only expected values 1 through n−1.

Brute force and the improvement

Scan the array separately for each value in 1..n: O(n²) time, O(1) space. A boolean presence array improves that to O(n) time with O(n) space. A sum difference also uses O(n) time and O(1) space if you calculate ((long) n * (n + 1L)) / 2 and the actual sum as long, not int. XOR reaches the same bounds without arithmetic overflow under the distinct-value contract.

Intuition

XOR has two useful properties: x ^ x is zero, and x ^ 0 is x. If we XOR every expected number with every number in the array, matching values cancel and the missing value remains.

Java solution

Java
public static int missingNumber(int[] values, int n) {
    int answer = n; // Include n; n−1 loop indexes provide expected values 1..n−1.

    for (int index = 0; index < values.length; index++) {
        answer ^= index + 1; // Include one expected range value.
        answer ^= values[index]; // Include one present value; equal values cancel.
    }
    return answer; // Only the missing number occurs once across the two sets.
}

Why not use the sum formula

The expected sum minus the actual sum is also correct, but an int sum can overflow for large input. XOR avoids that issue.

Dry run

Numbered illustrated dry run for Find the Missing Number; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

For n = 5 and [1, 2, 4, 5], start with answer = 5.

Index XOR expected Answer then XOR present Answer afterward
0 1 4 1 5
1 2 7 2 5
2 3 6 4 2
3 4 6 5 3

The intermediate accumulator is not a partial missing-number answer. Cancellation guarantees the final result 3 only after including both complete sets.

Complexity

Time is O(n) and extra space is O(1).

Common mistake

Make sure the expected range matches the problem. Some versions use values from 0 through n, while this version uses 1 through n.

Practice next

Next lessonLongest Subarray with Sum K

Practice using stored state to avoid repeated work.

Back to Arrays →