Missing Number

NeetCode: Missing Number · LeetCode: 268. Missing Number · Difficulty: Easy

Given an array nums of n distinct numbers taken from 0 to n inclusive, return the only number in that range that is missing.

Example

Text

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

Brute force: check every candidate

For each candidate from 0 to n, scan the array for it. The one that is never found is the answer. The nested scan makes this O(n²); sorting first would give O(n log n).

Java

public class Main {
    static class Solution {
        public int missingNumber(int[] nums) {
            int n = nums.length;
            for (int candidate = 0; candidate <= n; candidate++) {
                boolean found = false;
                for (int v : nums) {
                    if (v == candidate) {
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    return candidate;
                }
            }
            throw new IllegalStateException("exactly one number in 0..n is missing");
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.missingNumber(new int[]{3, 0, 1}));
        System.out.println(s.missingNumber(new int[]{0, 1}));
        System.out.println(s.missingNumber(new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1}));
        System.out.println(s.missingNumber(new int[]{0}));
    }
}

Output

Time: O(n²). Space: O(1).

Optimal: XOR indices against values

XOR all the numbers from 0 to n and all the array values. Every number that is present shows up twice and cancels, and the missing one shows up only once. Start the accumulator at n and XOR in i ^ nums[i] for each index, which covers 0 to n - 1 plus the extra n in a single pass. (Summing and subtracting from n(n+1)/2 works as well, but a sum of many terms can overflow int for large n, while XOR never overflows.)

Java

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

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.missingNumber(new int[]{3, 0, 1}));
        System.out.println(s.missingNumber(new int[]{0, 1}));
        System.out.println(s.missingNumber(new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1}));
        System.out.println(s.missingNumber(new int[]{0}));
    }
}

Output

Time: O(n). Space: O(1).