Repeat and Missing Number Array

The problem

Given an array of size n containing numbers from 1 to n, one number appears twice and another is missing. Find both.

Every expected number from 1 to n can pair with its appearance in the input. If you take the difference between expected and actual sums, and expected and actual sums of squares, the duplicate and missing values become two unknowns in a system of two linear equations that solve cleanly.

Full solution

XOR partitioning: XOR the array with 1..n to get repeating ^ missing, then split every number by the lowest set bit so the two unknowns land in separate buckets. Same O(n)/O(1) as the sum-of-squares trick but with no overflow to worry about, which is why it is the one to write.

def repeat_and_missing(arr: list[int]) -> tuple[int, int]:
    """Returns (repeating, missing) using XOR partitioning, O(1) extra space."""
    n = len(arr)
    xor_all = 0
    for i, v in enumerate(arr):
        xor_all ^= v ^ (i + 1)  # every value paired with its expected 1..n counterpart
    # xor_all == repeating ^ missing; they differ at the lowest set bit
    low_bit = xor_all & -xor_all
    a = 0  # XOR of everything with low_bit set
    b = 0  # XOR of everything with low_bit clear
    for i, v in enumerate(arr):
        a, b = (a ^ v, b) if v & low_bit else (a, b ^ v)
        k = i + 1
        a, b = (a ^ k, b) if k & low_bit else (a, b ^ k)
    # {a, b} == {repeating, missing}; a scan of arr decides which is which
    repeating = a if a in arr else b
    return repeating, xor_all ^ repeating

function repeatAndMissing(arr) {
  const n = arr.length;
  let xorAll = 0;
  for (let i = 0; i < n; i++) xorAll ^= arr[i] ^ (i + 1); // pair each value with expected 1..n
  // xorAll === repeating ^ missing; they differ at the lowest set bit
  const lowBit = xorAll & -xorAll;
  let a = 0; // XOR of everything with lowBit set
  let b = 0; // XOR of everything with lowBit clear
  for (let i = 0; i < n; i++) {
    if (arr[i] & lowBit) a ^= arr[i]; else b ^= arr[i];
    const k = i + 1;
    if (k & lowBit) a ^= k; else b ^= k;
  }
  // {a, b} === {repeating, missing}; a scan of arr decides which is which
  const repeating = arr.includes(a) ? a : b;
  return [repeating, xorAll ^ repeating];
}

The theory behind it

Arrays — the ground this problem stands on. All Arrays problems

What Arrays is

An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.

When to reach for it

Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.

How the pattern works

Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.

What each operation costs

Which roles need this problem

Arrays is a core topic for these 25 roles — if you're targeting one of them, this problem is early in your path, not optional.

Secondary for 3 more roles, including Database Engineer, Bioinformatics Engineer, Networking Engineer.