Plus One
You are given a large integer as an array digitsdigits[i]
The limits are 1 <= digits.length <= 1000 <= digits[i] <= 9long
Example 1
Output: [1, 2, 4]
Example 2
Output: [4, 3, 2, 2]
Example 3
Output: [1, 0]
Explanation: 9 + 1 = 10, which needs one more digit.
How to Think About It
Step 1: Why not convert to a number
Building an intlong
Step 2: Adding one only touches a tail of nines
Start at the last digit. If it is less than 9, add 1 and you are done: no carry is created, so nothing to its left changes. That is the common case, and it costs a single step.
Step 3: A 9 becomes 0 and passes the carry on
If the digit is 9, then 9 + 1 = 10: write 0 and carry 1 to the next digit on the left. Repeat. The carry stops at the first digit from the right that is not 9, so 1299 becomes 1300.
Step 4: The all-nines case
If every digit is 9, the loop turns them all into 0 and the carry falls off the left end. The answer is 1 followed by n zeros, which needs a new array one longer than the input. This is the only input where the length changes.
Walkthrough
The input digits = [1, 9, 9]
| i | digits[i] | Action | Array after |
|---|---|---|---|
| 2 | 9 | write 0, carry 1 | [1, 9, 0] |
| 1 | 9 | write 0, carry 1 | [1, 0, 0] |
| 0 | 1 | 1 < 9, so write 2 and return | [2, 0, 0] |
For [9, 9, 9][1, 0, 0, 0]
Java Solution
The method walks from the last digit to the first, turning nines into zeros until it finds a digit it can raise by one.
- The carry is implicit: while the loop runs, a carry of 1 is always waiting to be added. Reaching index i means every digit to its right was a 9 that is now a 0.
- Early return: a digit below 9 absorbs the carry, so the method returns right there. For
the loop runs once.[1, 2, 3] - All nines: reaching the code after the loop means every digit was 9. A new
array is filled with zeros by Java, so onlyint needs to be set.result[0] = 1 - In place: the method changes the input array and returns it in every case except all nines.
becomes[0] .[1]
A common mistake is to return digits[9, 9, 9][0, 0, 0][9][0]
public class PlusOne {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits; // no carry left, the digits to the left stay the same
}
digits[i] = 0; // 9 + 1 = 10: write 0 and carry 1 to the left
}
int[] result = new int[digits.length + 1]; // every digit was 9, e.g. 999 + 1 = 1000
result[0] = 1;
return result;
}
}
Complexity
- Time: O(n), where n is the number of digits. The loop visits each digit at most once from the right, and it stops at the first digit below 9. Only an all-nines input visits every digit and then fills a new array.
- Space: O(1) extra in every case but one, because the digits are changed in place. The all-nines input needs a fresh array of n + 1 digits, which is also the size of the answer.
The method matched BigInteger