Why it works
- A column adds at most three ones: two digits and the carry, so sum is 0, 1, 2 or 3, which is 00, 01, 10 or 11. Its low bit, sum & 1, is the digit of the answer, and the bit above it, sum >> 1, is the carry.
- A number that runs out simply adds 0, so a and b may have any lengths and the shorter one needs no padding.
- The loop also runs while carry = 1: in our example the last carry turns into the leading 1, and the answer is a digit longer than both numbers.
Complexity
Time O(n + m): one pass over the digits of a and b, plus at most one more column for the last carry. Memory O(max(n, m)) for the answer itself; everything else is a few numbers.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗