290. One Missing, One Repeated
Core1000 ms256 MBSolved by 0%
An array of n values should contain every integer from 1 to n exactly
once. In fact one value appears twice and one is missing entirely.
Print the repeated value and then the missing one, separated by a space.
1 2 2 4 -> 2 3
Because the values are guaranteed to lie between 1 and n, a counting array
indexed by value works and needs no hashing at all. That is worth noticing:
when the keys are small consecutive integers, an array IS the fastest possible
hash table.
Constraints - `2 ≤ n ≤ 200000` - `1 ≤ a[i] ≤ n` - Exactly one value repeats and exactly one is missing.
Input
The first line contains an integer n.
The second line contains n integers, each between 1 and n.
Output
Print the repeated value and the missing value, separated by a space.
Input4
1 2 2 4
Output2 3
Noteis the worked example
Input2
2 2
Output2 1
Noteis the smallest case, missing the first value
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.