JavaScript: LeetCode 'Plus One' recursion timeout problem-CodePudding

Plus one- leetcode problem

Problem:

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123   1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9   1 = 10.
Thus, the result should be [1,0].

Constraints:

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's.

My solution:

// [9] becomes [1,0]
var plusOne = function(digits) {
    let len = digits.length;
    //count array backwards
    for(let i = len-1; i >= 0; i--) {
        // if the currently indexed value is 9, we will zero it (line 14)
        // we will also check if the previous entry is 9 via recursion (line 19)
        // if it is not 9, we increment it by 1 and return 'digits' (lines 22, 23)
        // if there is no previous entry we prepend one and return 'digits' (lines 16, 17)
        if(digits[i] == 9) {
            digits[i] = 0;
            if(!digits[i - 1]){
                digits.unshift(1);
                return digits;
            } else {
                plusOne(digits.slice(0, i-1));
            }
        } else {
            digits[i] = digits[i]   1;
            return digits;
        }
    }
};

let array = [9,9,9];

console.log(plusOne(array));

// This code breaks on input:
// [9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]

The difficulty with this problem is with 9's, which naturally increment the place value of its more significant neighbor.

I address this problem with recursion. (As you can read in the code comments).

The problem is that I am getting a 'Time limit exceeded' error on Leetcode on the following input:

[9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9].

Though it appears to pass all other test cases.

Is this a stack size issue? Is there a way to optimize the space complexity of the above code?

Thank you very much.

I have no idea how to reduce the time/space complexity of the problem as I am new to recursion.

CodePudding user response：

"Is there a way to optimize the space complexity of the above code?"

Yes, remove the unnecessary recursive call. It does nothing:

// [9] becomes [1,0]
var plusOne = function(digits) {
    let len = digits.length;
    //count array backwards
    for(let i = len-1; i >= 0; i--) {
        // if the currently indexed value is 9, we will zero it (line 14)
        // we will also check if the previous entry is 9 via recursion (line 19)
        // if it is not 9, we increment it by 1 and return 'digits' (lines 22, 23)
        // if there is no previous entry we prepend one and return 'digits' (lines 16, 17)
        if(digits[i] == 9) {
            digits[i] = 0;
            if(i === 0){
                digits.unshift(1);
                return digits;
            }
        } else {
            digits[i] = digits[i]   1;
            return digits;
        }
    }
};

let array = [9,9,9];

console.log(plusOne(array));

CodePudding user response：

There's no need to traverse the entire input. The function can stop as soon as there's no carry to the next decimal place.

var plusOne = function(digits) {
  // a single digit add that returns [sum, carry]
  const incr = num => num === 9 ? [0, 1] : [num   1, 0];
  // reverse the input so we can go least significant to most
  const reversed = digits.reverse();
  let index = 0,
    carry = 0,
    sum = 0;

  // increment digits, stopping as soon as there's no carry
  // worst case is a run through a lot of 9s  
  do {
    [sum, carry] = incr(reversed[index]);
    reversed[index] = sum;
  } while (carry &&   index < reversed.length)

  // push a 1 if we got to the most significant digit with a carry
  if (carry) reversed.push(1);
  return reversed.reverse();
}

// here it is running pretty fast on 10x the largest input
let lottaNines = Array(1000).fill(9);
console.log(plusOne(lottaNines))

CodePudding user response：

you can do that :

const plusOne = arr =>
  {
  let 
    rem = 1
  , res = []
    ;
  for (let i=arr.length-1; i >= 0; i--)
    {
    res[i] = arr[i]   rem;
    rem    = res[i] > 9 ? 1 : 0;
    if (rem)
      res[i] = 0;
    }
  if (rem )
    res.unshift(1);
  return res;
  }

console.log( JSON.stringify(plusOne([1,2,3])))
console.log( JSON.stringify(plusOne([9])))
 
const outOfMaxInteger =[9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]

console.log( JSON.stringify(plusOne(outOfMaxInteger)))

you can also create a plus_N(arr,n) function (where n must be < 10)

const plus_N = (arr,add) =>
  {
  let 
    rem = add  // value must be < 10
  , res = []
    ;
  for (let i=arr.length-1; i >= 0; i--)
    {
    res[i] = arr[i]   rem;

    if (res[i] < 9)
      {
      rem = 0;
      }
    else
      {      
      rem     = 0 | (res[i] / 10);
      res[i] %= 10;
      }
    }
  if (rem)
    res.unshift(rem);
    
  return res;
  }

console.log( JSON.stringify(plus_N( [1,2,3],1))  , ' = [1,2,3]  1' )
console.log( JSON.stringify(plus_N( [9],1))      , ' = [9]  1'     )
console.log( JSON.stringify(plus_N( [1,2,3],7))  , ' = [1,2,3]  7' )
console.log( JSON.stringify(plus_N( [9],5))      , ' = [9]  5'     )