Crack the Backend

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range [0, n] that is missing from the array. There is exactly one missing number. n = nums.length, so the range has n+1 numbers and the array has n of them.

Sum approach: The sum of 0 + 1 + ... + n is n*(n+1)/2. The sum of nums is missing exactly one number. So missing = n*(n+1)/2 - sum(nums).
XOR approach: XOR has the property that x ^ x = 0. If we XOR all indices 0..n and all values in nums, every number that appears in both (index and value) cancels; the only number that appears once (the missing one, as an index) remains. So xor = 0; for i in 0..n xor ^= i; for x in nums xor ^= x; return xor.

Key Observations

Sum: expectedSum = n * (n + 1) / 2, actualSum = sum(nums), return expectedSum - actualSum. Watch for integer overflow for large n (use long or XOR).
XOR: Initialize xor = 0. For i from 0 to n, xor ^= i. For each x in nums, xor ^= x. Return xor. No overflow issue.

Approach

High-level (Sum): n = nums.length, expectedSum = n * (n + 1) / 2, actualSum = sum of nums. Return expectedSum - actualSum.

Steps (XOR): n = nums.length, xor = 0. For i = 0..n: xor ^= i. For each x in nums: xor ^= x. Return xor.

Implementation

Java

public int missingNumber(int[] nums) {
    int n = nums.length;
    int expected = n * (n + 1) / 2;
    int actual = 0;

    for (int x : nums) {
        actual += x;
    }

    return expected - actual;
}

Test Cases

Example 1

Input

nums = [3,0,1]

Expected

2

Explanation

n=3, range [0,3], 2 is missing.

Complexity Analysis

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

Follow-ups

Find duplicate and missing (one duplicate, one missing in 1..n).