Plus One
Problem Statement
You are given an integer array digits
, where each digits[i]
is the ith
digit of a large integer. It is ordered from most significant to least significant digit, and it will not contain any leading zero.
Return the digits of the given integer after incrementing it by one.
Example 1:
Input: digits = [1,2,3,4]
Output: [1,2,3,5]
Explanation 1234
+ 1
= 1235
.
Example 2:
Input: digits = [9,9,9]
Output: [1,0,0,0]
Constraints:
1 <= len(digits) <= 100
0 <= digits[i] <= 9
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(1)
space, where n
is the number of digits.
Hint 1
Consider what happens when the last digit is 9.
Hint 2
Think about how to handle the case where all digits are 9.
Solution
Iteration (Optimal)
def plus_one(digits: list[int]) -> list[int]: n = len(digits) for i in range(n - 1, -1, -1): if digits[i] < 9: digits[i] += 1 return digits digits[i] = 0
return [1] + digits
Time complexity: O(n)
Space complexity: O(1)