Pattern visualizer
Find the Missing and Repeating Number
Values are 1..n and indices are 0..n-1, so value v has one obvious home: cell v-1. Walk the array and keep swapping the value under the cursor into its home; the cursor only advances once the value sitting there is already home, or once home is blocked by an identical value. That block is the duplicate announcing itself. When the placement pass ends, exactly one cell disagrees with A[k] = k+1, and it names both answers at once: the value it holds is the repeated one, and its own position plus one is the missing one. Sign-marking solves the same problem in the same bounds and leaves magnitudes intact; this method scrambles the order instead, which is the right trade only when the caller does not need the input back. Animated on: A = [3,1,2,5,4,6,6] should hold 1..7 but one value repeats and one is absent — find both..
Cyclic placement — send every value to its own index
A=[3,1,2,5,4,6,6] should be a permutation of 1..7, but one value shows up twice and one never shows up. Because every legal value v has exactly one home — cell v-1 — the array can be sorted by PLACEMENT rather than comparison: keep sending each value home and the two anomalies fall out of the one cell that stays wrong.
1FUNCTION findMissingAndRepeating(A)2 i <- 03 WHILE i < LENGTH(A)4 home <- A[i] - 15 IF A[i] != A[home]6 SWAP A[i] AND A[home]7 ELSE8 i <- i + 19 FOR j <- 0 TO LENGTH(A) - 110 IF A[j] != j + 111 RETURN A[j], j + 1
← / → step · space play · Home restart