Plus One

Plus One to a Number Represented as an Array of Digits is a problem that comes up frequently in coding interviews and algorithm challenges. The task is simple: you are given an array of digits representing a non-negative integer, and you need to add 1 to this number. After adding, the result should still be represented as an array of digits. This problem tests your understanding of arrays, carry-over logic, and how to handle large numbers that don't fit into standard integer data types. Whether you're preparing for a coding interview or practicing array manipulation, mastering this problem will strengthen your skills in mathematical operations with arrays. In this lesson, we will cover the best approaches to solve this problem, ensuring that you can handle cases like carry overflow and arrays of different lengths.

Steps to Solve the "Plus One to a Number" Problem:

• Understand the Problem:
  • You are given an array where each element is a digit of a number.
  • The task is to add 1 to the number represented by the array and return the result as an array of digits.
  • You need to handle cases where the addition causes a carry-over, like turning 999 into 1000.
• Start from the Rightmost Digit:
  • Begin adding 1 starting from the rightmost digit (the least significant digit).
  • If the digit is less than 9, simply add 1 and return the updated array.
  • If the digit is 9, set it to 0 and carry over the 1 to the next digit.
• Handle Carry Overflow:
  • If all digits are 9, like in the case of [9, 9, 9], every digit will turn to 0, and you will need to add an extra digit at the beginning of the array to represent the result (e.g., [1, 0, 0, 0]).
• Edge Case Considerations:
  • Handle cases where the array only has one digit (e.g., [9] becomes [10]).
  • Ensure the solution works for arrays of varying lengths, including cases with leading zeros (though usually not present in valid inputs).
• Efficient Solution:
  • You can solve this problem in a single pass through the array, making it efficient with O(n) time complexity, where n is the number of digits in the array.
  • Space Complexity: O(1) if you modify the array in place, or O(n) if you need to create a new array for the result.

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 Python 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!