🎨Now live: Try our Free AI Image Generation Feature

Description
The plusOne
function takes a vector of integers representing a non-negative integer with each digit stored in a separate element. The function increments this integer by one and returns the resulting vector of digits.
Intuition
To increment the integer represented by the vector, we start from the least significant digit (rightmost) and add one. If the addition causes a digit to roll over from 9 to 0, we propagate this carry to the next more significant digit.
Approach
- Traversal from End: Start iterating from the last digit of the vector.
- Digit Handling: - If the digit is less than 9, simply increment it and return the updated vector. - If the digit is 9, set it to 0 and move to the next more significant digit.
- Overflow Handling: - If all digits are processed and all were 9s, insert a new digit (1) at the beginning of the vector to handle the carry-over.
Complexity
Time Complexity:
O(n), where n
is the number of digits in the vector. Each digit is processed at most once.
Space Complexity:
O(1) if we disregard the space used to return the new vector. The modification is done in-place.
Code
C++
class Solution {
public:
std::vector plusOne(std::vector& digits) {
int n = digits.size();
// Start from the last digit
for (int i = n - 1; i >= 0; --i) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
digits.insert(digits.begin(), 1);
return digits;
}
};
Python
class Solution:
def plusOne(self, 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] + [0] * n
Java
class Solution {
public int[] plusOne(int[] digits) {
int n = digits.length;
for (int i = n - 1; i >= 0; --i) {
if (digits[i] < 9) {
digits[i]++;
return digits;
}
digits[i] = 0;
}
int[] result = new int[n + 1];
result[0] = 1; // The new most significant digit
return result;
}
}
JavaScript
var plusOne = function (digits) {
let res = BigInt(digits.join(""))
let inc = String(BigInt(res)+1n)
//console.log(inc)
let t = inc.toString().split("").map(Number)
return t
};