Plus One
Plus One is a easy arrays & hashing problem solved with the right to left traversal pattern.
The best approach, optimal (in place, stop at the first non-9), runs in O(n) time and O(1) extra (O(n) only for the all-9s case) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (full carry pass into a new list) up.
Problem
A non-negative integer is stored as an array digits, one decimal digit per element, with the most significant digit first. Add 1 to the number and return the result in the same digit-array form.
The number can be much longer than any built-in integer type, so work with the digits directly.
Examples
Example 1
- Input
digits = [3, 0, 7]- Output
[3, 0, 8]- Why
- 307 + 1 = 308; only the last digit changes.
Example 2
- Input
digits = [2, 9, 9]- Output
[3, 0, 0]- Why
- 299 + 1 = 300; the carry ripples through both trailing 9s.
Example 3
- Input
digits = [9, 9]- Output
[1, 0, 0]- Why
- 99 + 1 = 100, which needs one more digit than the input.
Constraints
1 <= digits.length <= 1000 <= digits[i] <= 9digitshas no leading zeros, except for the number 0 itself ([0]).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (full carry pass into a new list) | O(n) | O(n) |
| Optimal (in place, stop at the first non-9) | O(n) | O(1) extra (O(n) only for the all-9s case) |
1Brute force (full carry pass into a new list)
O(n)Every digit is visited even when the carry dies out immediately.O(n)A separate list holds all result digits.Simulate schoolbook addition over every digit without stopping early: carry starts at 1, each digit becomes (d + carry) % 10, and the results are collected into a fresh list that is reversed at the end.
- carry = 1; walk i from n - 1 down to 0.
- sum = digits[i] + carry; append sum % 10 to a list; carry = sum / 10.
- If carry is still 1 after the loop, append 1.
- Reverse the list and copy it into an int array.
class Solution {
public int[] plusOne(int[] digits) {
List<Integer> out = new ArrayList<>();
int carry = 1;
for (int i = digits.length - 1; i >= 0; i--) {
int sum = digits[i] + carry;
out.add(sum % 10);
carry = sum / 10;
}
if (carry == 1) out.add(1);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) {
res[i] = out.get(out.size() - 1 - i);
}
return res;
}
}class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
out = []
carry = 1
for i in range(len(digits) - 1, -1, -1):
s = digits[i] + carry
out.append(s % 10)
carry = s // 10
if carry == 1:
out.append(1)
out.reverse()
return outclass Solution {
public:
vector<int> plusOne(vector<int>& digits) {
vector<int> out;
int carry = 1;
for (int i = (int)digits.size() - 1; i >= 0; i--) {
int sum = digits[i] + carry;
out.push_back(sum % 10);
carry = sum / 10;
}
if (carry == 1) out.push_back(1);
reverse(out.begin(), out.end());
return out;
}
};function plusOne(digits) {
const out = [];
let carry = 1;
for (let i = digits.length - 1; i >= 0; i--) {
const sum = digits[i] + carry;
out.push(sum % 10);
carry = Math.floor(sum / 10);
}
if (carry === 1) out.push(1);
return out.reverse();
}2Optimal (in place, stop at the first non-9)
O(n)The loop stops at the first non-9 from the right; the worst case touches all n digits.O(1) extra (O(n) only for the all-9s case)The input is updated in place; a new array is needed only when the length grows.Walk from the right. A digit below 9 just gets incremented and the array is returned immediately. A 9 turns into 0 and the loop continues. Only when the loop finishes is every digit 9, so the answer is a new array of length n + 1 that starts with 1 and is zero elsewhere.
- For i from n - 1 down to 0: if digits[i] < 9, increment it and return digits.
- Otherwise set digits[i] = 0.
- After the loop, create res of length n + 1, set res[0] = 1, return res.
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;
}
int[] res = new int[digits.length + 1];
res[0] = 1;
return res;
}
}class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1
return digits
digits[i] = 0
return [1] + [0] * len(digits)class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
for (int i = (int)digits.size() - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
vector<int> res(digits.size() + 1, 0);
res[0] = 1;
return res;
}
};function plusOne(digits) {
for (let i = digits.length - 1; i >= 0; i--) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
const res = new Array(digits.length + 1).fill(0);
res[0] = 1;
return res;
}Edge cases to test
- All digits are 9: the answer is a 1 followed by n zeros
- The single digit [0]
- Trailing 9s inside a longer number, like [4, 9, 9]
- Up to 100 digits, far beyond what a long can hold
Hints
Hint 1
Do it the way you add by hand: start at the last digit and carry to the left.
Hint 2
As soon as a digit is not 9, add 1 to it and you are done. A 9 becomes 0 and the carry moves on.
Hint 3
If the carry falls off the front, every digit was 9.
FAQ
What is the best time complexity for Plus One?
Optimal (in place, stop at the first non-9) runs in O(n) time and O(1) extra (O(n) only for the all-9s case) extra space. The loop stops at the first non-9 from the right; the worst case touches all n digits.
Which pattern does Plus One use?
It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.
Is there a brute force solution for Plus One?
Yes. Brute force (full carry pass into a new list) takes O(n) time and O(n) space. Simulate schoolbook addition over every digit without stopping early: carry starts at 1, each digit becomes (d + carry) % 10, and the results are collected into a fresh list that is reversed at the end.
Which edge cases should I test for Plus One?
All digits are 9: the answer is a 1 followed by n zeros; The single digit [0]; Trailing 9s inside a longer number, like [4, 9, 9]; Up to 100 digits, far beyond what a long can hold.