3 ms·
Your 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 s
by brohee 15y ago
Your 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 15y 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.