Task
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input:
[1,2,3]
Output:
[1,2,4]
Explanation:
The array represents the integer 123.
Example 2:
Input:
[4,3,2,1]
Output:
[4,3,2,2]
Explanation:
The array represents the integer 4321.
This problem was taken from Leetcode
Solution
The solution:
The solution is pretty straight forward. We traverse all digits in the opposite direction, and make sure that we add +1 only on the last digit (the first iteration ). Then if the digit > 9 we set up the dit to 0, and we carry on 1 to add it to the next digit, and keep going till we reach the first digit. If the first digit is 9 and cary over is not 0, we add 1 to the beginning of the array.
let’s consider: 9 9 9
iteration 1:
9 9
9 9
9 + 1 = 0 + cary on: 1
iteration 2:
9 9
9 + 1 = 0 + cary on: 1
0 0
iteration 3:
9 + 1 = 0 + cary on: 1
0 0
0 0
finally:
1 << adding leading 1
0
0
0
which gave up the final result: 1 0 0 0
The solution will look like this:
Java Script
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
var carryOn = 0;
for(q = digits.length - 1; q!=-1; q--) {
var digit = digits[q];
if(q == digits.length - 1) {
digit = digit + 1;
if(digit == 10) {
digit = 0;
carryOn = 1;
}
}
else {
if(digit == 9 && carryOn) {
digit = 0;
}
else {
digit = digit + carryOn;
carryOn = 0;
}
}
digits[q] = digit;
}
if(carryOn > 0)
digits.unshift(1);
return digits;
};
what we just did:
– (lines 11 – 18) happened only if this is the last digit, where we have to add 1
– (lines 18 – 20) if we have carry on value of carryOn > 0 and digit = 9 simply set digit = 0 and left carryOn to be equal to 1 for the next iteration.