Question

Formatted question description: https://leetcode.ca/all/66.html

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

@tag-array

Algorithm

If the number at the end is 9, then there will be a carry problem, and if the number in the previous digit is still 9, you need to continue to advance. The specific algorithm is as follows:

first judge whether the last digit is 9, if not, add one directly to return,
if it is, then assign 0 to the digit, and then continue to check the previous digit, the same method, until the first digit is checked.
If the first digit was originally 9, a new digit will be generated after adding one, then the last thing to do is to check whether the first digit after the calculation is 0, if it is, add a 1 to the top.

Code

Java

public class Plus_One {

    public class Solution_clean {
        public int[] plusOne(int[] digits) {
            int n = digits.length;
            for (int i = digits.length - 1; i >= 0; --i) {
                if (digits[i] < 9) {
                    ++digits[i];
                    return digits;
                }
                digits[i] = 0; // digits[i] is 9
            }
            int[] res = new int[n + 1]; // only reaching here when input is straigh 9s, like [9,9,9,9,9]
            res[0] = 1;
            return res;
        }
    }

    public class Solution {
        public int[] plusOne(int[] digits) {

            if (digits == null || digits.length == 0) {
                return digits;
            }

            // just note overflow, and when carray array size +1
            int carry = 1; // initate as 1, as to the "plus one"

            for (int i = digits.length - 1; i >= 0; i--) {

                int add = carry + digits[i];

                if (add >= 10) {
                    carry = add / 10;
                    add = add % 10;
                } else {
                    carry = 0;
                }

                digits[i] = add;
            }

            // final check
            if (carry > 0) {
                // increase int[] size
                int[] sizePlusOne = new int[digits.length + 1];
                sizePlusOne[0] = carry;

                // fill the rest
                for (int i = 1; i < sizePlusOne.length; i++) {
                    sizePlusOne[i] = digits[i - 1];
                }

                digits = sizePlusOne;
            }
            // System.out.println(Arrays.toString(digits));
            return digits;
        }
    }

}

// OJ: https://leetcode.com/problems/plus-one/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> plusOne(vector<int>& A) {
        int i = A.size() - 1, carry = 1;
        for (; i >= 0 && carry; --i) {
            carry += A[i];
            A[i] = carry % 10;
            carry /= 10;
        }
        if (carry) A.insert(begin(A), carry);
        return A;
    }
};

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):
            digits[i] += 1
            digits[i] %= 10
            if digits[i] != 0:
                return digits
        return [1] + digits

############

class Solution(object):
  def plusOne(self, digits):
    """
    :type digits: List[int]
    :rtype: List[int]
    """
    carry = 1
    for i in reversed(range(0, len(digits))):
      digit = (digits[i] + carry) % 10
      carry = 1 if digit < digits[i] else 0
      digits[i] = digit
    if carry == 1:
      return [1] + digits
    return digits

66 - Plus One

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions