digits the dashed slot on the left is only used if the number grows a digit
public int[] plusOne(int[] digits) { int n = digits.length; for (int i = n - 1; i >= 0; i--) { if (digits[i] < 9) { digits[i]++; return digits; } digits[i] = 0; // 9 becomes 0, carry 1 } int[] res = new int[n + 1]; res[0] = 1; return res;}
- i
- —
- digits[i]
- —
- carry
- 1
Why it works
- Converting to a number and back fails in Java: the array can hold more digits than a
long(19 digits) can, so it would overflow. The point is to do the arithmetic yourself. - Only the trailing 9s change much: adding 1 to the last digit either just bumps it (digit < 9, and you are done) or turns a 9 into 0 and carries 1 to the left. The carry keeps moving only through 9s.
- Return early: the first digit below 9 absorbs the carry, and nothing to its left changes. Worst case, all 9s, touches every digit: O(n) time, O(1) extra space.
- Pitfall: all 9s. The loop ends with every digit 0 and a carry still pending. The number needs one more digit: return a new array one longer with
res[0] = 1(Java zero-fills it), so[9,9,9]becomes[1,0,0,0]. - Related: Add Binary, Add Strings and Add Two Numbers use the same carry loop with a general sum
a + b + carry; Multiply Strings carries per digit product.