3 ms·
You could return the 0s with a carry flag.
by ericbarrett 3y ago
You 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.