3 ms·
I don’t see how you can increment `9999` in O(1) if the string length is considered the size of the input. You have to rewrite the string with zeroes, which is
by ninkendo 3y ago
I don’t see how you can increment `9999` in O(1) if the string length is considered the size of the input. You have to rewrite the string with zeroes, which is O(n) of the size of the string.
- jeffbee 3y agoFor that case, which is the worst case, yes. And the amortized average complexity is O(1) because that case is unlikely. Are you starting to see why this is a good icebreaker? It has all kinds of discussion potential.
- ninkendo 3y agoNo, not when the goal is to actually implement it. You implied in your comment that if I wasn’t someone who could implement this in 15 seconds, I’m not a good candidate in your mind. It would take me longer to explain why it’s not trivial.
- ericbarrett 3y agoYou could return the 0s with a carry flag.
- jeffbee 3y agoIt's still O(N) even if you don't need to copy the input, because you nonetheless visited every character in the string.
- ericbarrett 3y agoOh, I skimmed over the O(1) part. That baffled me for a moment, then I realized you were talking about the general case of a uniform random input where a carry for the 1s digit has probability 0.1, a carry for the 10s digit 0.01, etc., and all 9s is the pathological worst case, right? That's what I get for coming into the discussion sideways.