Plus One to a Number Represented as an Array of Digits

Imagine you’re at a party, and it’s time to count the number of guests. But instead of writing down the total number directly, you decide to represent it in a fun way, using individual digits. For example, if there are 123 guests, you’d write it as [1, 2, 3]. Now, what if one more guest arrives? How do you add one to this number? This is exactly what we’ll explore in this blog.

Adding one to a number represented as an array of digits might sound simple, but it can be a bit tricky, especially when carrying is involved. Let’s explore this problem step by step and understand how we can solve it efficiently.

Problem statement

You’re given a number represented as an array of digits, where each digit is an element of the array. Your task is to add one to this number and return the result as a new array.

Sample input

1digits = [1, 2, 3]

Sample output

1[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].

Understanding the problem

Adding one to a number seems easy, but when the number is represented as an array of digits, we need to carefully handle each digit, especially when dealing with carries. For example, if the number is [9, 9, 9], adding one will result in [1, 0, 0, 0]. Here, all the digits turn to 0, and a new digit 1 is added to the front.

Brute force approach

The simple way to start is by adding one to the last digit of the array. If the last digit is less than 9, we simply increment it and return the array. But if the last digit is 9, it becomes 0, and we need to carry the one to the next digit. We continue this process for each digit until there’s no carry left.

Special case

If all the digits in the array are 9, like [9, 9, 9], after processing all the digits, we’ll have a carry left. In this case, we need to add a new digit 1 at the beginning of the array.

Pseudo algorithm

• Start from the last digit and move towards the first digit.
• Add one to the last digit.
• If the last digit becomes 10, set it to 0 and carry over one to the next digit.
• Repeat the process until there are no more carryovers.
• If there is a carryover after processing all digits, insert a new digit 1 at the beginning of the array.
• Return the resulting array of digits.

Python code

Let’s start with the straightforward approach.

1def add_one(digits):
2    n = len(digits)
3    
4    for i in range(n - 1, -1, -1):
5        if digits[i] < 9:
6            digits[i] += 1
7            return digits
8        digits[i] = 0
9    
10    return [1] + digits

Explanation

• We start from the last digit of the array and add one.
• If the digit is less than 9, we simply increment it and return the array.
• If the digit is 9, we set it to 0 and move to the next digit, carrying the one.
• If all digits are processed and we still have a carry, we add a new digit 1 at the front.

Java code

1public class AddOneToArray {
2    public static int[] addOne(int[] digits) {
3        int n = digits.length;
4        
5        for (int i = n - 1; i >= 0; i--) {
6            if (digits[i] < 9) {
7                digits[i]++;
8                return digits;
9            }
10            digits[i] = 0;
11        }
12        
13        int[] newDigits = new int[n + 1];
14        newDigits[0] = 1;
15        return newDigits;
16    }
17}

C++ code

1#include <vector>
2
3std::vector<int> addOne(std::vector<int>& digits) {
4    int n = digits.size();
5    
6    for (int i = n - 1; i >= 0; i--) {
7        if (digits[i] < 9) {
8            digits[i]++;
9            return digits;
10        }
11        digits[i] = 0;
12    }
13    
14    digits.insert(digits.begin(), 1);
15    return digits;
16}

Explanation

• The logic is the same in Python, Java, and C++.
• We handle each digit starting from the last one, managing the carry as we go.
• If all digits turn to 0 (like in [9, 9, 9]), we add a new digit 1 at the front.

Efficient approach

The approach we’ve discussed is already efficient with a time complexity of O(n), where n is the number of digits in the array. Since we only pass through the array once, there’s no need for further optimization.

Conclusion

Adding one to a number represented as an array of digits is a simple yet interesting problem. It teaches us how to handle carries and how to think about numbers in a different way. By breaking the problem down into smaller steps, we can easily manage even the trickiest cases, like when all digits are 9.

Whether you’re coding in Python, Java, or C++, the approach remains the same. Understanding this problem will not only help you in solving similar problems but also strengthen your grasp of basic programming concepts.

So, next time you encounter a problem that seems easy but has hidden challenges, remember to break it down and tackle it step by step. Happy learning!