DiffPush Tier Arrays · Hard O(N) · O(1)
A warehouse manifest should list tracking numbers 1 through N exactly once, but one number was scanned twice and another was skipped entirely. The scanner can no longer produce a clean list, so reconciliation must recover both the duplicated number and the missing one from the dirty manifest.
Input: An integer N and an array Arr of N integers taking values in [1, N].
Output: Two values: the number that occurs twice, followed by the number that never occurs.
2 <= N <= 10^51 <= Arr[i] <= NSums may exceed 32-bit rangeInput: {"N":2,"Arr":[2,2]}
Output: [2,1]
The manifest repeats 2, which forces 1 to be the number that was never scanned.
Input: {"N":4,"Arr":[1,2,2,4]}
Output: [2,3]
Everything matches the clean manifest except the duplicated 2 and the absent 3.