Add One to a Big Integer Stored as Digits

easy array math

Problem

An array digits holds a non-negative integer with the most significant digit first (no leading zeros except the number 0 itself). Return an array representing the integer digits + 1.

Inputdigits = [9,9,9]

Output[1,0,0,0]

Walk right-to-left. If the digit is < 9, increment and stop. Otherwise set it to 0 and keep going. If the carry propagates past the front, prepend a 1.

digits (comma-separated)

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

function plusOne(digits) {
  for (let i = digits.length - 1; i >= 0; i--) {
    if (digits[i] < 9) {
      digits[i]++;
      return digits;
    }
    digits[i] = 0;
  }
  return [1, ...digits];
}

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) { digits[i]++; return digits; }
            digits[i] = 0;
        }
        int[] out = new int[digits.length + 1];
        out[0] = 1;
        return out;
    }
}

vector<int> plusOne(vector<int>& digits) {
    for (int i = (int) digits.size() - 1; i >= 0; i--) {
        if (digits[i] < 9) { digits[i]++; return digits; }
        digits[i] = 0;
    }
    digits.insert(digits.begin(), 1);
    return digits;
}

Time: O(n) Space: O(1) in place (or O(n) with a leading 1)