Plus One
Problem Descriptionβ
Given a non-negative number represented as a list of digits, add 1
to the number (increment the number represented by the digits). The digits are stored such that the most significant digit is first element of array.
Examplesβ
Example 1:
Input:
N = 3
arr[] = {1, 2, 4}
Output:
1 2 5
Explanation:
124+1 = 125, and so the Output
Example 2:
Input:
N = 3
arr[] = {9,9,9}
Output:
1 0 0 0
Explanation:
999+1 = 1000, and so the output
Your Taskβ
You don't need to read input or print anything. You only need to complete the function increment()
that takes an integer N, and an array arr of size N as input and returns a list of integers denoting the new number which we get after adding one to the number denoted by the array arr.
Expected Time Complexity:
Expected Auxiliary Space: for iterative approach.
Constraintsβ
1 β€ n β€ 10^5
Problem Explanationβ
Given a non-negative number represented as a list of digits, add 1
to the number (increment the number represented by the digits). The digits are stored such that the most significant digit is first element of array.
Code Implementationβ
- Python
- C++
- Javascript
- Typescript
- Java
def increment(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
return digits
digits.insert(0, 1)
return digits
vector<int> increment(vector<int>& digits) {
for (int i = digits.size() - 1; i >= 0; --i) {
if (digits[i] == 9) {
digits[i] = 0;
} else {
digits[i]++;
return digits;
}
}
digits.insert(digits.begin(), 1);
return digits;
}
function increment(digits) {
for (let i = digits.length - 1; i >= 0; --i) {
if (digits[i] === 9) {
digits[i] = 0;
} else {
digits[i]++;
return digits;
}
}
digits.unshift(1);
return digits;
}
function increment(digits) {
for (let i = digits.length - 1; i >= 0; --i) {
if (digits[i] === 9) {
digits[i] = 0;
} else {
digits[i]++;
return digits;
}
}
digits.unshift(1);
return digits;
}
public List<Integer> increment(List<Integer> digits) {
for (int i = digits.size() - 1; i >= 0; --i) {
if (digits.get(i) == 9) {
digits.set(i, 0);
} else {
digits.set(i, digits.get(i) + 1);
return digits;
}
}
digits.add(0, 1);
return digits;
}
Time Complexityβ
- The iterative approach has a time complexity of .
Space Complexityβ
- The space complexity is since we are using only a fixed amount of extra space.