4 ms·
There's an O(1) solution for stoi?
by za3faran 4y ago
There's an O(1) solution for stoi?
- jeffbee 4y agoNo, but there is an O(1) solution to the problem of incrementing a non-negative integer represented as an ASCII string, if you modify the string in place. I won't spoil the fun for you. Note that the "solution" that ChatGPT proposes as O(1) is not in fact O(1) because it copies the input to the output which is necessarily O(N) regardless of how much dodgy logic is inside the function.
- heeen2 4y agodoesn't that still depend on the length of the input string? If I feed it a billion 9s it still has to look at all of them. Am I missing an obvious shortcut?
- scatters 4y agoAmortised constant is over all inputs, and almost all natural numbers are not 1 less than a power of 10. Of course, you need to start at the correct end, otherwise it's logarithmic just to get there.
- hneryhhh 4y agoHm, I can't see it. 9999999.... requires n steps to modify it to 10000.....