Pattern visualizer
Repeat and Missing Number Array
The constraint that every value lies in 1..n is the whole gift: a value is also an address. Walk the array and, for each value v, flip the sign of cell v-1 to mean "v has been seen". A cell that is already negative when you reach it means its value arrived twice, and after the walk the one cell still positive names the value that never arrived. Reads take ABS so a cell the cursor has not visited yet can be marked safely. The sum-and-sum-of-squares identity solves the same problem without touching the input, but its squares overflow on large n; this trades that risk for temporarily scrambled signs. Animated on: A = [4,6,6,3,1,7,5] holds the numbers 1..7 with exactly one value repeated and one missing — find both..
The array indexes itself — signs as checkboxes
A=[4,6,6,3,1,7,5] holds the numbers 1..7, one of them twice and one not at all. Every value is itself a legal index here — value v belongs in cell v-1 — so the array can carry its own bookkeeping: flipping cell v-1 negative records "v has been seen", and no second structure is needed.
1FUNCTION repeatAndMissing(A)2 FOR i <- 0 TO LENGTH(A) - 13 v <- ABS(A[i])4 IF A[v - 1] < 05 repeat <- v6 ELSE7 A[v - 1] <- -A[v - 1]8 FOR j <- 0 TO LENGTH(A) - 19 IF A[j] > 010 missing <- j + 111 RETURN repeat, missing
← / → step · space play · Home restart