An array arr of size n was supposed to hold each number from 1 to n exactly once — but something went wrong. One value from the range appears twice, and one value from the range is missing entirely.
Find both. Return an array of two integers, repeating first, missing second: [repeating, missing].
[repeating, missing]. Swapping them fails the tests even though both values are correct.1..n with nothing missing at all.arr (it flips entries negative). If mutation is forbidden, use the frequency-array approach, a math/XOR variant, or restore the signs with one extra abs pass at the end.sum(arr) - n(n+1)/2 = R - M, and the sum of squares gives R² - M² = (R - M)(R + M); two equations, two unknowns. Use 64-bit arithmetic (the square sum reaches ~3.3 × 10^17). Alternatively, XOR all elements with 1..n to get R ^ M, then split by the lowest set bit into two groups to separate R from M.1..n into its own hash map.Input: arr = [2, 2] Output: [2, 1] 2 appears twice, and 1 never appears.
Input: arr = [1, 3, 3] Output: [3, 2] 3 appears twice, and 2 never appears.
Input: arr = [4, 3, 6, 2, 1, 1] Output: [1, 5] 1 appears twice, and 5 never appears.
- 2 <= n <= 10^6 - 1 <= arr[i] <= n - Exactly one value repeats and exactly one value is missing
One value vanished and another quietly took its place. The problem looks like simple bookkeeping, but it hides one of the most reusable array tricks in interviews: when values live in 1..n, the array can act as its own hash map.
In plain English: arr should contain each of 1..n exactly once, but one number sneaked in twice and pushed another out. Formally: given arr of size n with 1 <= arr[i] <= n, exactly one value occurs twice and exactly one value from 1..n never occurs — return [repeating, missing].
Worked example — arr = [4, 3, 6, 2, 1, 1] (n = 6)
value: 1 2 3 4 5 6
count: 2 1 1 1 0 1
↑ ↑
double-booked empty
answer: [1, 5]
Two or three sharp questions before coding show the interviewer you design for the contract, not just the happy path.
“Is it guaranteed that exactly one value repeats and exactly one is missing?”
Yes — every approach below leans on this promise. Without it you would need general duplicate and gap detection.
“Are all values guaranteed to lie between 1 and n?”
Yes — that guarantee is exactly what makes value-as-index tricks safe.
“Which number comes first in the answer?”
The repeating number first, then the missing one: [repeating, missing]. Swapping them is a silent wrong answer.
“How large can n get?”
Up to 10^6 — checking every candidate with a fresh scan is about 10^12 operations, so you need a linear approach.
“Am I allowed to modify the input array?”
If yes, sign-marking gives O(1) extra space. If not, fall back to a frequency array or a math/XOR variant.
Before I start, I have a few clarifying questions.
Can I assume exactly one value is duplicated and exactly one is missing, with every element between 1 and n?
Should I return the repeating number first, and am I allowed to modify the input array in place?
There are n slots and the values are drawn from 1..n — so value v has a natural home: index v - 1. In a perfect array each value would visit its own home exactly once. Ours has one home visited twice and one never visited.
value v ──▶ index v - 1 [4, 3, 6, 2, 1, 1]: both 1s point at index 0; nothing points at index 4
Every value is positive, so the sign of each entry is unused space. Negating arr[v - 1] when you see v is a one-bit visited flag that costs no extra memory. Arrive at a slot that is already negative, and v has been seen before — v is the repeating number.
After the marking pass, every value that appeared has flipped its home negative. The one index i still positive was never visited by anyone — so missing = i + 1 falls out of a single final scan.
| Brute force | Counting | Sign marking | |
|---|---|---|---|
| Time | O(n²) | O(n) | O(n) |
| Space | O(1) | O(n) | O(1) |
Full, runnable code for every approach lives in the Approaches selector below.
Key takeaway
When an array's values are confined to 1..n, the array can index itself — value-as-index plus sign-marking turns it into a hash map you get for free. One pass flips signs to expose the duplicate; one scan finds the home left untouched.
for each entry x in arr:
v = |x|
if arr[v-1] < 0: repeating = v
else: arr[v-1] = -arr[v-1]
for i in 0..n-1:
if arr[i] > 0: missing = i + 1
return [repeating, missing]