Plus One
Problem
Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
digits = [9,9,9][1,0,0,0]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] + digitsfunction 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;
}Explanation
Adding one to a number stored as digits is just like doing it by hand: you start at the rightmost digit and handle any carry that ripples leftward.
We walk from the last index toward the first. If the current digit is less than 9, we can simply increment it and we are done — there is no carry, so we return immediately.
If the digit is 9, adding one turns it into 10, so we set it to 0 and let the carry move one step left to the next digit.
If the loop runs off the front (every digit was a 9), the carry has nowhere to go, so we prepend a 1 to the front, like [9,9,9] becoming [1,0,0,0].
Example: digits = [9, 9, 9]. Each 9 becomes 0 as the carry propagates, and after the front we add a leading 1, giving [1, 0, 0, 0].