Add one to a very large integer

Question

I was asked to implement this in an interview a while back. I didn't pass the interview, mostly likely because it took me far too long to do. However, I'm interested to know how well implemented the actual code is.

The task was to:

Add one to a positive number represented as an array of integers.

The question is the same as this one. However, I have done it in JavaScript and my implementation is different (recursion rather than loops), so I hope they are sufficiently different.

var addToArray = function(n){
    var result = [];

    function carryOne(n) {
        if (n.length === 0) {
            result.push(1);
        }
        else {
            var length = n.length-1;
            if (n[length] < 9) {
                n[length] += 1;
                result.push(n);
            } else {
                result.push(0);
                carryOne(n.slice(0, length));
            }
        }
    }
    carryOne(n);
    result.reverse();
    var flatten = Array.prototype.concat.apply([], result);
    console.log(flatten);
}

I've just noticed I have missed the semicolons on the closing braces on the function definitions but I'm keeping it like that for honesty.

In general it works but I think the need to reverse and flatten the array at the end is quite inelegant, so I suspect there is a better solution.

Answer 1

I agree with the other answers, it's a bit over-engineered. That's usually caused by the lack of knowledge in the language's native API. Not to worry, every one has encountered this situation at least once in their job interview days. Mine was "In any language, reverse a string in as few lines of code as possible". Only after my interview did I discover that there was strrev.

The first problem I see is that your iteration of the original array is in one direction, while adding digits in to result is in another direction. This causes you to end up doing an unnecessary reverse. Instead of push, why not unshift which adds to the beginning of the array instead of the end? That way, both operations are in the same direction.

The next one was looking for the array of integers that you mentioned. It was only after I saw n.length did I realize that n was an array. Make your variables verbose, name them so everyone knows what it's for.

Then I'm not really sure what the purpose of the last concat is. Isn't result already an array?

Anyways, took a shot at your problem. There is actually a reduceRight in JS which is perfect for this. It's the same as reduce, only it starts from the end of the array.

var number = [1,9,9,9];


function addOne(array) {
  // I wouldn't want to mutate the original array, so I slice
  var arrayCopy = array.slice();
  
  // `reduceRight` acts like `reduce`, except it starts from the end.
  // It's also like `forEach` except it allows you to carry a value.
  arrayCopy.reduceRight(function(carry, current, index) {
    
    // Add normally
    var sum = current + carry;
    
    // Update our carry
    carry = (sum / 10) | 0;
    
    // Update the current digit in the array
    arrayCopy[index] = sum % 10;
    
    // If we're at the last digit and we have a carry, add it in
    if(index === 0 && carry !== 0) arrayCopy.unshift(carry)
    
    // Return the carry for the next operation
    return carry

  // Here's our "add one"
  }, 1);
  
  return arrayCopy;
}

// You can optionally add .join('') to get a string instead.
var result = addOne(number);

document.write(JSON.stringify(result));

Answer 2

The whole code is overengeneered, very much so in my opinion. The code can be reduced to:

function digitsIncrement(digits) {
    return toDigits(fromDigits(digits) + 1);
}

The two functions mentioned are easy to write, should take 1 to 5 lines each and be immediately understandable.

Remember to convert to a common format, calculate and convert back instead of working in a weird format.

Answer 3

Two big problems with the given solution are:

• It modifies the input array in some cases
• It doesn't return anything

Here's another way of attacking the problem:

• Make a copy of the input array
• Starting from the right, zero out all consecutive nines
• If the input was all nines, we prepend 1 to the array
• Otherwise, we increment the current digit (the right-most non-nine digit)

var addOne = function(n) {
    var result = n.slice();
    var i = n.length - 1;
    while (i >= 0 && result[i] == 9) {
        result[i] = 0;
        i--;
    }

    // At this point, n[i + 1] ... n[n.length - 1] = 9.
    if (i == -1) {
        result.unshift(1);
    } else {
        result[i]++;
    }
    return result;
}

Answer 4

Here's an approach which uses reduce to build up the result number, and avoids the special case "if...else" logic.

Note that as soon as we hit a digit that doesn't carry over, add becomes 0 and the remaining digits are returned unaltered. Also, using the modulus operator % lets us avoid having to treat 9 as a special case.

Also note we reverse the array and then un-reverse when we're done. This is simply so that we can work with reduce, which traverses the array in order from left to right, whereas in our case we need right to left traversal because we start with the least significant digit.

function addOne(arr) {
  arr = arr.slice();
  var add = 1, newDigit, result;

  // add a leading 0 so we don't have to do a special case when
  // the most significant digit is 9
  result = arr.reverse().concat(0).reduce(function(m, digit) {
    newDigit = (digit + add) % 10;
    add = (newDigit == 0) ? 1 : 0;
    return m.concat(newDigit);
  }, []).reverse();

  // remove the leading 0 unless we've used it
  if (result[0] == 0) result.shift();
  return result;
}