3 ms·
It's still O(N) even if you don't need to copy the input, because you nonetheless visited every character in the string.
by jeffbee 3y ago
It'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.