Plus One
Asked at Google
Problem
You are given a large integer represented as an integer array digits, where each digits[i] is the i-th digit of the number (most significant digit first). Increment the integer by one and return the resulting array of digits. The array does not contain any leading zeros except for the number zero itself.
Asked At
| Company | Difficulty | |
|---|---|---|
| EASY | View all Google questions → |
How to Think About It
Brute force: convert the array to an integer, add one, convert back to an array — risks overflow for very large inputs.
Handle carry: start from the least significant digit, add one, and propagate carry to the left.
Optimize for no-carry case: if the last digit is not 9, simply increment it and return — covers most cases in O(1).
Handle all-9s case: if every digit is 9, the result has one more digit (e.g., 999 becomes 1000), so create a new array.
Optimal: O(n) time, O(1) extra space (or O(n) if a new array is needed for the all-9s case). Single pass from right to left.
Optimal Approach
Traverse the digits array from right to left. If a digit is less than 9, increment it by one and return immediately (no carry to propagate). If the digit is 9, set it to 0 and continue to the next digit (carry propagates). If the loop completes, every digit was 9, so create a new array of size n+1 with the first digit as 1 and the rest as 0. This runs in O(n) time and uses O(1) extra space in the common case.
What Trips People Up in Real Interviews
Start with the simplest case: last digit is not 9. Show you handle the easy path first.
Discuss the all-9s edge case explicitly — this is where most bugs happen.
Ask whether the input can be empty or very large to show you think about constraints.
Avoid converting to an integer type if the number of digits is very large — stay array-based.
Mention that this is a great warm-up for carry-propagation problems like adding two numbers.
Solution Code
def plusOne(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] < 9:
digits[i] += 1
return digits
digits[i] = 0
return [1] + digitsFrequently Asked Questions
What is the Plus One problem?
You are given a large integer represented as an integer array digits, where each digits[i] is the i-th digit of the number (most significant digit first). Increment the integer by one and return the resulting array of digits. The array does not contain any leading zeros except for the number zero itself.
How do you solve Plus One?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Plus One?
Plus One is asked at Google. It is a easy difficulty problem.
What are common mistakes on Plus One?
- Start with the simplest case: last digit is not 9. Show you handle the easy path first.
- Discuss the all-9s edge case explicitly — this is where most bugs happen.
- Ask whether the input can be empty or very large to show you think about constraints.
- Avoid converting to an integer type if the number of digits is very large — stay array-based.
- Mention that this is a great warm-up for carry-propagation problems like adding two numbers.