← DSA Foundations
easyArray Basics (1D)

Find Missing Number

An array of n distinct integers contains values from 0 through n, with exactly one missing. Find that value.

LeetCode ↗

Work through the cases

3 examples

Input notation

One nonempty line of space-separated integers.

Expected result

The missing integer.
Case 1

Input

0 3 1

Expected output

2
Case 2

Input

1

Expected output

0
Case 3

Input

0 1 2

Expected output

3

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

One value from [0,n] is missing. XOR the indices 1..n with the array entries; pairs cancel and the missing number remains.

The XOR operation has the following properties:

- Any number XOR 0 is still the original number, i.e., x \oplus 0 = x; - Any number XOR itself is 0, i.e., x \oplus x = 0;

Therefore, we can traverse the array, perform XOR operation between each element and the numbers [0,..n], and the final result will be the missing number.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int ans = n;
        for (int i = 0; i < n; ++i) {
            ans ^= (i ^ nums[i]);
        }
        return ans;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.