Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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


}
share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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]
share|improve this answer
1  
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. –  La-comadreja Mar 3 at 23:02
    
@rolfl Thanks for your comment –  bazang Mar 3 at 23:15
    
@rolfl can you test your code with {3, 9, 9}; I don't think it works. –  bazang Mar 3 at 23:20
    
I have, and it works fine –  rolfl Mar 3 at 23:42
1  
@palacsint absolutely, I'd love to help out.I like it here. –  bazang Apr 1 at 19:16
show 4 more comments

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;
}
share|improve this answer
    
in the corner case of the overflow, digits should be copied to retVal –  vals Mar 3 at 22:41
    
int[] values are automatically initialized to 0 @vals –  La-comadreja Mar 3 at 22:42
    
never mind @vals. done. –  La-comadreja Mar 3 at 22:46
    
I mean for (int i = 1; i < retVal.length; i++) retVal[i] = digits[i-1]; –  vals Mar 3 at 22:49
    
@La-comadreja Your code doesn't work. Pass int[] a={9, 9} as input, the answer should be {1, 0, 0} –  bazang Mar 3 at 22:50
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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