Find All Numbers Disappeared in an Array

Given an array of n integers where every value is in 1..n (some appearing twice, some not at all), return every number in 1..n that's missing — in O(n) time and O(1) extra space (the output array doesn't count).

Example

Input: 4 3 2 7 8 2 3 1 Output: 5 6

Approach

Same cyclic-sort placement as Missing Number, adjusted for a 1-indexed range: value v's home index is v - 1. After sorting every value into place (skipping duplicates, which simply can't both occupy the same home), scan once — every index i whose value isn't i + 1 marks a missing number i + 1.

Input format

Line 1: the array, space-separated

Print every missing number, space-separated (an empty line if none are missing).