Plus One

Problem Description

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.

Increment the large integer by one and return the resulting array of digits.

Examples

Constraints

• 1 ≤ digits.length ≤ 100
• 0 ≤ digits[i] ≤ 9
• digits does not contain any leading 0’s.

Traverse Backwards and Handle Carries

Iterate through the array from right to left:

1. If the current digit is less than 9, increment it by 1 and return the array immediately.
2. If the current digit is 9, it becomes 0. Continue the loop to add the carry to the next digit.

If the loop finishes and all digits have become 0 (e.g., input was [9, 9, 9]), we need to create a new array of size n + 1, set the first element to 1, and return it.

Solution: Backwards Iteration

class Solution {
    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;
        }

        // if we reach here, all digits were 9
        int[] result = new int[n + 1];
        result[0] = 1;
        return result;
    }
}

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0

        # if we reach here, all digits were 9
        return [1] + digits

#include <vector>

class Solution {
public:
    std::vector<int> plusOne(std::vector<int>& digits) {
        int n = digits.size();
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }

        // if we reach here, all digits were 9
        std::vector<int> result(n + 1, 0);
        result[0] = 1;
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of digits. The loop terminates at the first non-9 digit.
• Space Complexity: O(N) in the worst case (e.g. all 9s) to create the new array, otherwise O(1) in-place.

← All Problems