Find the Repeated and Missing Number
You get an array nums of size n. It should contain every number from 1 to n exactly once. But one number appears twice, and because of that, one other number is missing.
Return an array [repeated, missing]: first the number that appears twice, then the number that does not appear.
The array is not always sorted.
Hint
A simple way: mark each value as seen in an array of size n + 1. The value you see a second time is the repeated one, and the value never marked is the missing one.
With O(1) extra space: compare the sum of nums with the sum of 1..n. That gives repeated - missing. Do the same with the sum of squares to get a second equation.
Examples
Example 1
- Input:
- [4,2,6,1,2,5]
- Output:
- [2,3]
n = 6. The value 2 appears twice and the value 3 does not appear.
Example 2
- Input:
- [1,1]
- Output:
- [1,2]
n = 2. The value 1 appears twice, so 2 is missing.
Example 3
- Input:
- [3,5,4,2,5]
- Output:
- [5,1]
n = 5. The value 5 appears twice and 1 is missing.
Constraints
2 <= n == nums.length <= 401 <= nums[i] <= n- Exactly one value appears twice, exactly one value from
1..nis missing, and every other value appears once.
Run checks your code against the 3 examples. Submit checks it against all 253 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.