#66
Plus One
Easy Carry handling
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A large integer is stored as an array of digits, most significant first. Add one and return the new digit array.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: add 1 to a big number stored as a digit array.
Why this works: like adding on paper from the right. A 9 becomes 0 and carries; the first non-9 just goes up by one.
Example: [1, 2, 9, 9]
9 → 0 (carry), 9 → 0 (carry)2 → 3, stop[1, 3, 0, 0]
✦Hints open one at a time
Start from the last digit. If it's below 9, just increment and stop.
A 9 becomes 0 and the carry moves left.
If every digit was 9, you need a new array one longer.
↗Approach
Walk from the end. The first digit that isn't 9 absorbs the +1 and we return. If the loop finishes, the number was all 9s, so return 1 followed by zeros.
</>Solution (Java)
class Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0; // 9 + 1 = 10, carry continues
}
int[] res = new int[digits.length + 1];
res[0] = 1; // 999 -> 1000
return res;
}
}!Common mistake
Converting the digits to an int or long — the array can be 100 digits long.
Complexity
- Time: O(n).
- Space: O(1), or O(n) in the all-9s case.
Topic: Arrays
