Skip to content
AI360Xpert
Back to Math & Geometry
Easy

Plus One

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

Input:digits = [1,2,3]
Output:[1,2,4]
The array represents the integer 123. Incrementing by one gives 123 + 1 = 124. Thus, the result should be [1,2,4].
Input:digits = [4,3,2,1]
Output:[4,3,2,2]
The array represents the integer 4321. Incrementing by one gives 4321 + 1 = 4322. Thus, the result should be [4,3,2,2].
Input:digits = [9]
Output:[1,0]
The array represents the integer 9. Incrementing by one gives 9 + 1 = 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.

Schoolbook Addition

Approach

We iterate through the array from right to left (least significant digit to most). If the current digit is less than 9, we simply increment it by 1 and return the array, because no carry will be propagated further left. If the current digit is 9, incrementing it makes it 10, so we set it to 0 and the loop continues to the next digit to the left (carrying over the 1). If we finish the loop and haven't returned, it means all digits were 9 (like `[9, 9, 9]`). In this case, we need to add a new leading `1` (making it `[1, 0, 0, 0]`).

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(1)

Time complexity is O(n) as we might iterate through all digits. Space complexity is O(1) in the average case (modifying in place) and O(n) in the worst case (e.g., all 9s, creating a new array).

Solution.java
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 made it here, all digits were 9        int[] newNumber = new int[n + 1];        newNumber[0] = 1;        // The rest of the elements in newNumber are initialized to 0 by default in Java        return newNumber;    }}