Plus One — Solution in Python, Java & C++
Plus One solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Google.
Plus One is an easy coding problem on arrays and math, asked in Amazon, Google, Meta and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Math
- Asked at: Amazon, Google, Meta, TCS, Apple, Intuit, Spotify
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a large integer represented as an integer array digits, where each digits[i] is the i-th digit, ordered most significant first. The integer has no leading zeros.
Increment the integer by one and return the resulting array of digits.
Example 1
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: 123 + 1 = 124.
Example 2
Input: digits = [4,3,9]
Output: [4,4,0]
Explanation: The 9 rolls over and carries into the 3.
Example 3
Input: digits = [9,9]
Output: [1,0,0]
Explanation: Every digit rolls over, so the result is one digit longer.
Constraints
1 <= digits.length <= 400 <= digits[i] <= 9digits does not contain leading zeros.
Hints for Plus One
Hint 1
Walk from the last digit backwards.
Hint 2
A digit below 9 can absorb the increment — bump it and you are done immediately.
Hint 3
A 9 becomes 0 and the carry continues. If the loop runs off the front, every digit was a 9: prepend a 1.
How to solve Plus One
Walk from the least significant digit: the first digit below 9 absorbs the increment and the work stops there; every 9 before it rolls over to 0.
Approach
- Iterate
ifrom the last index down to 0. - If
digits[i] < 9, increment it and return the array immediately. - Otherwise set
digits[i] = 0and continue. - If the loop finishes, every digit was 9: return
[1] + digits.
Why it works
Adding one only carries while it hits 9s; the first non-9 digit stops the carry. If no digit stops it, the number was 99…9 and the answer is 100…0, one digit longer.
Complexity
- Time —
O(n) - Space —
O(1) extra (O(n) only when a new leading digit is needed)
Pitfalls
- Converting to an integer fails for arrays longer than the integer width.
- Forgetting the all-nines case returns
[0,0,…,0].
Reference solution
Python
def plusOne(digits):
d = list(digits)
for i in range(len(d) - 1, -1, -1):
if d[i] < 9:
d[i] += 1
return d
d[i] = 0
return [1] + dJava
public static int[] plusOne(int[] digits) {
int[] d = Arrays.copyOf(digits, digits.length);
for (int i = d.length - 1; i >= 0; i--) {
if (d[i] < 9) {
d[i]++;
return d;
}
d[i] = 0;
}
int[] out = new int[d.length + 1];
out[0] = 1;
return out;
}C++
vector<int> plusOne(vector<int>& digits) {
vector<int> d = digits;
for (int i = (int) d.size() - 1; i >= 0; i--) {
if (d[i] < 9) {
d[i]++;
return d;
}
d[i] = 0;
}
vector<int> out(d.size() + 1, 0);
out[0] = 1;
return out;
}JavaScript
var plusOne = function(digits) {
const d = digits.slice();
for (let i = d.length - 1; i >= 0; i--) {
if (d[i] < 9) {
d[i]++;
return d;
}
d[i] = 0;
}
return [1].concat(d);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays