4 ms·
Aren't the first two problems simple to solve: 1. create an array length n of booleans set to false, set the each index i to true for the integers in the array
by Gupie 14y ago
Aren't the first two problems simple to solve:
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?
- cncool 14y ago"create an array length n of booleans" This could have a space complexity of O(n), not O(1).
- thaumasiotes 14y agoyes, "create an array of length n" requires O(n) space.
- brohee 14y agoYour solution is in O(N) space, since you create a N sized array. 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).
- Robin_Message 14y agoI don't think it requires big integers. If you do it with machine words, the overflow/underflow will exactly cancel out so you will be fine. I think. 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.