7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Could you explain a little more how your algorithm works (with an example perhaps?). Because I feel like this algorithm doesn't work. \$\endgroup\$ – IEatBagels Oct 19 '15 at 19:19
  • \$\begingroup\$ If the final digit of the input array is 9 it adds zero to the result array and calls the function again on the input array minus the final digit. If the input array length reaches zero this means the most significant digit is also 9, so it adds a 1 to the result array. If the final digit is less than 9 it adds the array to the result. If you pass in something like [9,9,9,9,6,9,9,9,9] the results array ends up like [ 0, 0, 0, 0, [ 9, 9, 9, 9, 7 ] ], hence the need for the hacky last few lines. The first zero of the result array corresponds to the final 9 of the input array. \$\endgroup\$ – Thomas Barrett Oct 19 '15 at 20:51
1
\$\begingroup\$

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));

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is an awesome answer. I could see some interviewers thinking this was a "cheat," but I think it's perfect and like it better than my suggestion. Btw each of those functions could be implemented in 1 line with join and split and parseInt \$\endgroup\$ – Jonah Oct 19 '15 at 19:38
  • \$\begingroup\$ @Jonah If using built-in addition is forbidden why would you allow loops? :) But I get your point, they want to see if you can carry the remainder over the array with some loops, but they should have chosen something harder for that. Anyhow I think a serious interviewer would give you a lot of points for this for getting the simplest solution possible and not going immediately the obvious complicated route. \$\endgroup\$ – Caridorc Oct 19 '15 at 19:41
  • 1
    \$\begingroup\$ I agree. I certainly would. And I would not want to work for someone who didn't. \$\endgroup\$ – Jonah Oct 19 '15 at 19:43
  • 1
    \$\begingroup\$ I initially came up with something similar but they wanted it to work for numbers bigger than 2^64. Would your solution work for numbers that size? \$\endgroup\$ – Thomas Barrett Oct 19 '15 at 20:24
  • 1
    \$\begingroup\$ It's one thing to defeat the exercise, but if you do so in an interview question without mentioning the caveat, you're not getting the job. \$\endgroup\$ – 200_success Oct 19 '15 at 23:15
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ just a stylistic choice, but i think a ternary operator in place of the final if/else is nicer, turning 5 lines into 1 with no reduction in readability (imo). \$\endgroup\$ – Jonah Oct 20 '15 at 15:21
0
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ reverse reverses the array in-place, so the input array is modified. \$\endgroup\$ – mjolka Oct 20 '15 at 2:25

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.