10
\$\begingroup\$

I submitted this problem for an interview, and I was wondering if I could have done better. My solution works, and I solved in about 12-15 minutes. I feel like I did a bad job with the code. Please be honest.

Here is the question:

Given a non-negative number represented as an array of digits, plus one to the number. Also, the numbers are stored such that the most significant digit is at the head of the list.

In particular, what stumped me was the fact that I'd get the right answer, but have the initial index (at 0) in sometimes empty with the answer on the other half, and couldn't figure out a quick half to shift all the elements to the left without using extra storage.

public int[] plusOne(int[] digits) {
    int[] toRet=new int[digits.length+1]; 
    int[] temp=null;

    for(int i=toRet.length-1; i>=0; i--){
        if(i-1>=0){
            toRet[i]=digits[i-1];
        }
    }
    for(int i=toRet.length-1; i>=0; i--){
        if(toRet[i]+1 == 10){
            toRet[i]=0;
        }
        else{
            toRet[i] = toRet[i]+1;
            break;
        }
    }
    if(toRet[0]==0){
        temp = new int[toRet.length-1];
        for(int i=1; i<toRet.length;i++){
            temp[i-1] = toRet[i];
        }
       return temp;
    }
    else{
        return toRet;
    }


}
\$\endgroup\$
0

3 Answers 3

7
\$\begingroup\$

What you did well

I like that you have:

  • decently named varaibles
  • you use good backward looping through the data
  • the formatting and style is good.

Issues

  • you are doing a lot of manual copying... Arrays.copyOf() is your friend.
  • you should be declaring variables where you need them, not at the beginning of the method (temp).
  • the algorithm is not a natural fit for the problem.... too complicated, and that is why there is the odd offset in your results.

Alternative...

Consider this code alternative, which uses a standard adder-with-carry:

public static final int[] addOne(int[] digits) {
    int carry = 1;
    int[] result = new int[digits.length];
    for (int i = digits.length - 1; i >= 0; i--) {
        int val = digits[i] + carry;
        result[i] = val % 10;
        carry = val / 10;
    }
    if (carry == 1) {
        result = new int[digits.length + 1];
        result[0] = 1;
    }
    return result;
}

The carry is initialized with the value-to-add 1, and it is added to the least significant value.

If the overall addition results in a carry still, then we add a new digit to the result, and, because the sub being added is a 1, we can make assumptions about the result.

Edit:

My test code:

public static void main(String[] args) {
    System.out.println(Arrays.toString(addOne(new int[]{})));
    System.out.println(Arrays.toString(addOne(new int[]{1})));
    System.out.println(Arrays.toString(addOne(new int[]{9})));
    System.out.println(Arrays.toString(addOne(new int[]{3, 9, 9})));
    System.out.println(Arrays.toString(addOne(new int[]{3, 9, 9, 9})));
    System.out.println(Arrays.toString(addOne(new int[]{9, 9, 9, 9})));
    System.out.println(Arrays.toString(addOne(new int[]{9, 9, 9, 8})));
}

and my results:

[1]
[2]
[1, 0]
[4, 0, 0]
[4, 0, 0, 0]
[1, 0, 0, 0, 0]
[9, 9, 9, 9]
\$\endgroup\$
7
  • 1
    \$\begingroup\$ I like that. It's even more generalizable to make "carry" into an explicit parameter so you can add any one-digit number, not just 1. \$\endgroup\$ Mar 3, 2014 at 23:02
  • \$\begingroup\$ @rolfl can you test your code with {3, 9, 9}; I don't think it works. \$\endgroup\$
    – bazang
    Mar 3, 2014 at 23:20
  • \$\begingroup\$ Just realised from your solution that int arrays are initialized with 0s... don't think I've ever explicitly relied on this part of the JLS. :) If I was working on the solution as you, I will also check that the array is not empty so that my method doesn't return 1 for it... but this could be just me. ;) \$\endgroup\$
    – h.j.k.
    Mar 4, 2014 at 1:51
  • \$\begingroup\$ @rolfl I thought by saying 'new' in the if carry==1, you are essentially allocating a new slab of memory of the array, so it would lose the previous memory that variable was assigned to, yet somehow it retains it, how so? \$\endgroup\$
    – bazang
    Mar 4, 2014 at 18:22
  • 1
    \$\begingroup\$ @palacsint absolutely, I'd love to help out.I like it here. \$\endgroup\$
    – bazang
    Apr 1, 2014 at 19:16
1
\$\begingroup\$

The goal in my answer is code conciseness. Order of magnitude of runtime is the length of the array, which would only need to be re-created if the new array has additional digits. If you're only adding +1, it's somewhat simpler to perform the carry operation.

public int[] plusOne(int[] digits) {
    if (digits == null) return null;
    if (digits.length == 0) return new int[] {1};
    for (int i = digits.length - 1; i >= 0; i--) {
        if (digits[i] != 9) {
            digits[i]++;
            return digits;
        } else digits[i] = 0;
    }
    int[] retVal = new int[digits.length + 1];
    retVal[0] = 1;
    for (int i = 1; i < retVal.length; i++) digits[i] = 0;
    return retVal;
}
\$\endgroup\$
7
  • \$\begingroup\$ in the corner case of the overflow, digits should be copied to retVal \$\endgroup\$
    – vals
    Mar 3, 2014 at 22:41
  • \$\begingroup\$ int[] values are automatically initialized to 0 @vals \$\endgroup\$ Mar 3, 2014 at 22:42
  • \$\begingroup\$ never mind @vals. done. \$\endgroup\$ Mar 3, 2014 at 22:46
  • \$\begingroup\$ I mean for (int i = 1; i < retVal.length; i++) retVal[i] = digits[i-1]; \$\endgroup\$
    – vals
    Mar 3, 2014 at 22:49
  • \$\begingroup\$ @La-comadreja Your code doesn't work. Pass int[] a={9, 9} as input, the answer should be {1, 0, 0} \$\endgroup\$
    – bazang
    Mar 3, 2014 at 22:50
1
\$\begingroup\$

This is old, but I saw it today and I would do it differently.

int i = digits.length - 1;
while ((i >= 0) && (digits[i] == 9)) {
    i--
}

int[] results;
if (i < 0) {
    results = new int[digits.length + 1];
    results[0] = 1;
} else {
    results = new int[digits.length];
    System.arraycopy(digits, 0, results, 0, i);
    results[i] = digits[i] + 1;
}

return results;

Essentially there are two cases. In one, every digit is a nine. In that case, you need the results to be one longer than the input. And the answer is a one followed by [size of input] zeroes. In the other you have some number of nines followed by a digit less than nine. The digit less than nine increments by one.

Java defaults elements of a new int array to 0. So all the digits after i will be correct. We only need to se the digit at i and those before it. If i is negative, then there are no digits before it. Otherwise, we copy all digits before it to the new array.

One loop at the beginning finds the start of the string of nines at the end, it's one after i. The if/else handles our two cases. We only need to copy the digits that are not part of the ending nines. In the all nines case, nothing needs copied. In the other cases i digits are copied (potentially zero).

This method avoids any manual copying. It only does at most one addition on the input and no divisions or remainders. No temp variable (except i). It only allocates the amount of memory that is needed, whereas your original would allocate digits.length + 1 even if digits.length was enough.

In general, I think that results is a better name for an array than toRet.

This does assume that all the digits are in the range zero to nine. If not, this will produce incorrectly formatted results. The @rolfl method would fix most of the formatting. And then break if the carry was more than one at the end (which is not possible with validly formed input).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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