1. create an array length n of booleans set to false, set the each index i to true for the integers in the array, the index of one still false is the missing integer 2. same as 1 but with a count
Both are O(N) but perhaps my understanding of what constant space means is flawed?
The elegant solution to the first problem requires big integers in a realistic setting, and simply involves summing all the numbers and comparing with what the sum of 1 to n should be (n(n+1)/2 iirc).
If that's not true, then adding each x and subtract i as you process it is sufficient to ensure you only need integers comparable in size to N, not N^2.
This could have a space complexity of O(n), not O(1).