Plus One

Difficulty: Easy | Acceptance: 49.90% | Paid: No Topics: Array, Math

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, except for the number 0 itself.

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

• Examples
• Constraints
• Approach 1: Elementary Math
• Approach 2: Recursive Solution
• Approach 3: String Conversion

Examples

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 -> 124.
Thus, the result should be [1,2,4].

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 -> 4322.
Thus, the result should be [4,3,2,2].

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 -> 10.
Thus, the result should be [1,0].

Constraints

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's, except for the number 0 itself.

Approach 1: Elementary Math

Intuition We simulate the process of adding one starting from the least significant digit (the end of the array). If a digit becomes 10 after adding one, we set it to 0 and carry the 1 to the next more significant digit.

Steps

• Iterate through the array from the last element to the first.
• Add 1 to the current digit.
• If the digit is less than 10, return the array immediately as no further carry is needed.
• If the digit is 10, set it to 0 and continue the loop to carry the 1 to the next iteration.
• If the loop completes without returning, it means all digits were 9 (e.g., 99 becomes 100). In this case, insert a 1 at the beginning of the array.

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
        return [1] + digits

Complexity

• Time: O(n), where n is the number of digits. In the worst case (e.g., 999), we iterate through the entire array.
• Space: O(1) if we modify the array in-place, or O(n) if we create a new array in the case of all 9s (depending on language implementation).
• Notes: This is the most optimal approach for this problem.

Approach 2: Recursive Solution

Intuition We can solve this problem recursively by processing the array from the end towards the beginning. If the last digit is less than 9, we simply increment it. If it is 9, we set it to 0 and recursively call the function on the subarray excluding the last digit.

Steps

• Define a recursive helper function that takes the array (or a reference to it and an index).
• Base case: If the array is empty (or index is out of bounds), it means we have carried over past the most significant digit (e.g., 99 -> 100). Return a new array starting with 1.
• Check the last element of the current scope.
• If it is less than 9, increment it and return the result.
• If it is 9, set it to 0 and return the result of the recursive call on the rest of the array, appending the 0.

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        if not digits:
            return [1]
        if digits[-1] < 9:
            digits[-1] += 1
            return digits
        else:
            digits[-1] = 0
            return self.plusOne(digits[:-1]) + [0]

Complexity

• Time: O(n), as we may traverse the entire array in the worst case.
• Space: O(n) for the recursion stack in the worst case (e.g., 999…9).
• Notes: While elegant, the recursive approach uses more stack memory than the iterative approach and is generally not preferred for simple array iterations in production.

Approach 3: String Conversion

Intuition We can convert the array of digits into a string, parse that string into a large integer, add one to it, and then convert the result back into an array of digits. This leverages built-in language features for arithmetic and type conversion.

Steps

• Join the elements of the integer array into a single string.
• Convert the string to a numeric type capable of handling large integers (e.g., Python int, Java BigInteger, JavaScript BigInt).
• Add 1 to the numeric value.
• Convert the resulting number back to a string.
• Split the string into individual characters and map them back to integers to form the result array.

class Solution:
    def plusOne(self, digits: list[int]) -> list[int]:
        num_str = ''.join(map(str, digits))
        num = int(num_str) + 1
        return [int(d) for d in str(num)]

Complexity

• Time: O(n) for joining and splitting strings, though the underlying arithmetic operation may vary in cost depending on the size of the integer (up to 10¹⁰⁰).
• Space: O(n) to store the string representations of the numbers.
• Notes: This approach is often slower and uses more memory than the elementary math approach due to string manipulation overhead. It also requires handling large integers (BigInt) to avoid overflow errors.