# Add one to a number represented as an array of digits

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

}

-

# 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) {
}


and my results:

[1]
[2]
[1, 0]
[4, 0, 0]
[4, 0, 0, 0]
[1, 0, 0, 0, 0]
[9, 9, 9, 9]

-
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 '14 at 23:02
@rolfl Thanks for your comment – bazang Mar 3 '14 at 23:15
@rolfl can you test your code with {3, 9, 9}; I don't think it works. – bazang Mar 3 '14 at 23:20
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. ;) – h.j.k. Mar 4 '14 at 1:51
@palacsint absolutely, I'd love to help out.I like it here. – bazang Apr 1 '14 at 19:16

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

-
in the corner case of the overflow, digits should be copied to retVal – vals Mar 3 '14 at 22:41
int[] values are automatically initialized to 0 @vals – La-comadreja Mar 3 '14 at 22:42
never mind @vals. done. – La-comadreja Mar 3 '14 at 22:46
I mean for (int i = 1; i < retVal.length; i++) retVal[i] = digits[i-1]; – vals Mar 3 '14 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 '14 at 22:50