Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Missing Number

Problem (restated)

Array of n distinct numbers in [0, n]. Find the missing one.

Intuition

XOR of 0..n with all nums cancels pairs; leftover is missing.

Approaches

XOR 0..n with nums

Unverified

Time O(n)Space O(1)

Idea. x=0..n fold with nums.

Walkthrough. [3,0,1] → 2.

Trade-offs. Sum formula also O(n); XOR avoids overflow concerns in other langs.

Solution

export function missingNumber(nums: number[]): number {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i]!;
  return x;
}

export function missingNumber(nums: number[]): number {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i]!;
  return x;
}

Template connection

Bit XOR identity (same family as single number).

Reflection

XOR 0 through n together with every value in the array. Pairs cancel and the missing number remains. n * (n + 1) / 2 - sum(nums) is the same answer.
0 may be the missing value. n may be the missing value: the array holds n numbers from a range of n + 1. A single 0 means 1 is missing.
The sum can overflow. The XOR cannot.