Problem

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.

Examples

Example 1:

1
2
3
4
5

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

Example 2:

1
2
3
4
5

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

Example 3:

1
2
3
4
5

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

Solution

Method 1 - Iterative but naive

To solve this problem, we can use a flag to mark if the current digit needs to be changed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public int[] plusOne(int[] digits) {
	if (digits == null || digits.length == 0) {
		return new int[0];
	}

	int carry = 1;
	for (int i = digits.length - 1; i >= 0; i--) {
		int sum = digits[i] + carry;
		if (sum >= 10) {
			carry = 1;
		} else {
			carry = 0;
		}
		digits[i] = sum % 10;
	}

	if (carry == 1) {
		int[] result = new int[digits.length + 1];
		System.arraycopy(digits, 0, result, 1, digits.length);
		result[0] = 1;
		return result;
	} else {
		//int[] result = new int[digits.length];
		return digits;
	}
}

Method 2 - Iterative but check if all 9s

To increment a non-negative number represented as an array of digits:

  1. Traverse the array from the end to the beginning.
  2. Add one to the last digit. If the digit is less than 9, update it and return the array.
  3. If the digit is 9, set it to 0 and move to the next digit to the left.
  4. If you traverse the entire array and all digits were 9’s, set all digits to 0 and add 1 at the beginning of the array (e.g., 999 becomes 1000).

Approach

  1. Traverse the Array: Iterate from the last digit to the first.
  2. Addition and Carry Handling:
    • If the current digit is less than 9, increment it and terminate the function by returning the array.
    • If the current digit is 9, set it to 0 and move to the next digit.
  3. Handling Full Carry: If all digits are 0 after the loop, it means the number was composed entirely of 9’s. Create an array of length n + 1 with the first element as 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public 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;
        }
        
        int[] ans = new int[n + 1];
        ans[0] = 1;
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
        
        ans = [0] * (n + 1)
        ans[0] = 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(n),  where n is the number of digits.
  • 🧺 Space complexity: O(n) in the worst case when we need to add an additional digit for the carry over.