LeetCode 66 · Math & Geometry · concept: math-and-geometry
Problem
A number is given as an array of digits (most-significant first). Add one and return the resulting digit array.
[1,2,3] -> [1,2,4]
[9,9,9] -> [1,0,0,0]
Approach — carry from the right (optimal)
Walk from the last digit. If it’s less than 9, increment and you’re done — no carry propagates. If it’s 9, it becomes 0 and the carry moves left. If every digit was 9, prepend a leading 1.
def plusOne(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1
return digits # no carry beyond here -> done
digits[i] = 0 # 9 -> 0, carry continues
return [1] + digits # all 9s: e.g. 999 -> 1000Time O(n), space O(1) (or O(n) for the all-9s prepend).
The all-nines case
The only time the array grows is 9…9 → 10…0, needing a new leading digit. The early return on the first non-9 makes the common case cheap (stop as soon as the carry is absorbed); reaching the loop’s end means every digit carried.
Key insight
Grade-school arithmetic on a digit array → propagate a carry from the least-significant end, handling the length-growth edge case. Simple, but it’s the base-10 version of the carry logic in Add Two Numbers and Sum of Two Integers — carrying is the unifying idea.
Related
- concept: math-and-geometry
- relative: Add Two Numbers
- prev: Happy Number · next: Pow(x, n)
Software engineering
Infrastructure & security
Computer science
Hardware & engineering