3
\$\begingroup\$

The task

is taken from leetcode

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.

My solution

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
  let i = digits.length;
  let carry = 1;
  let tmp;
  const res = [];
  while(i > 0 || carry) {
    tmp = (--i >= 0 ? digits[i] : 0) + carry;
    carry = tmp / 10 | 0;
    res.unshift(tmp % 10);
  }
  return res;
};
\$\endgroup\$
2
\$\begingroup\$

Nice. Good use of the carry to add the 1.

One point. Arrays only grow from the end. Array.unshift() means that each item must be moved up and is \$O(n)\$ complexity (making the whole function approx \$O(n^{log(n)})\$ ) while Array.push() is only \$O(1)\$ but then you will have to reverse but would still be \$O(n)\$ overall.

You could also pre-allocate the array and slice the result array if there is no extra digit.

function plusOne(digits) {
    var i = digits.length, carry = 1, tmp;
    const res = [];
    while (i-- > 0 || carry) {
        tmp = (i >= 0 ? digits[i] : 0) + carry;
        carry = tmp / 10 | 0;
        res.push(tmp % 10);
    }
    return res.reverse();
}
  • If you must use function expressions use a const. Eg const plusOne = function
\$\endgroup\$
2
\$\begingroup\$

It looks like your logic is fine, but I don't find it very readable. I guess it would be fine if you could clearly explain your logic in a tech interview, but here's how I'd write it just to be more clear.

Use a for loop (that's what they're for!), modify the digits array in place unless they specify you shouldn't, and you can return as soon as you don't have anything left to carry.

var plusOne = function(digits){
    let carry=1;

    for(let i=digits.length-1; i>=0; i--){
        let digitSum = carry + digits[i];
        if(digitSum >= 10){
            digits[i] = digitSum%10;
        }
        else{
            digits[i] = digitSum;
            return digits;
        }
    }

    if(carry == 1){
        digits.unshift(1);
    }
    return digits;
}
\$\endgroup\$
  • \$\begingroup\$ You could save yourself the Else case . Or is there a reason why you wanted to include it? \$\endgroup\$ – thadeuszlay May 22 at 5:34
  • \$\begingroup\$ What are while loops for? Do you realize that a let i in a for loop means a new i is pushed to the heap, assigned the old value and operated on for every iteration, plus the one for the or loop prep. For loops with block scopes are more complex than while loops both in terms of source size and CPU load. \$\endgroup\$ – Blindman67 May 22 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.