LeetCode Problem 66 : Plus One

Question

I have started practicing problems in leetcode and I solved the following problem on LeetCode.

The challenge is :

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

 Example 1:
 Input: [1,2,3]
 Output: [1,2,4]
 Explanation: The array represents the integer 123.

 Example 2:
 Input: [4,3,2,1]
 Output: [4,3,2,2]
 Explanation: The array represents the integer 4321.

I am trying to get better at writing good code for my solutions. Please give me your suggestions

class Solution {
    public int[] plusOne(int[] a) {


        int length = a.length-1;

        while(length>=0)
        {
            a[length]=a[length]+1;
            int carry = a[length]/10;
            if(carry==1)
            {
                a[length]=0;
                length=length-1;
            }
            else
                break;
        }

        if(a[0]==0)
        {
            int [] array = new int[a.length+1];
            array[0]=1;
            for(int i=1;i<array.length-1;i++)
            {
                array[i]=0;
            }
            return array;
        }
        return a;

    }
}

Answer 1

The way you handle the extra digit for the last carry seems clumsy to me. To my mind, it would be much better to include the extra digit, by creating a new array at the start, then discard the extra digit if it's not needed.

Having that array for the answer, allows you to use it to hold the carry if needed.

When you know the numeric limits to your loop, it is much better to use a for loop rather than a while loop. This keeps the relative information for the loop in one place.

Putting this together it could look like this:

public int[] plusOne(int[] digits) {
    int newLength = digits[0] == 9 ? digits.length + 1 : digits.length;
    int[] answer = new int[newLength];
    int a = newLength - 1;
    answer[a] = 1;
    for (int d = digits.length - 1; d >= 0; --d, --a) {
        answer[a] += digits[d];
        if (answer[a] == 10) {
            answer[a] = 0;
            answer[a-1] = 1;
        }
    }
    return answer[0] > 0 ? answer : Arrays.copyOfRange(answer, 1, newLength);                
}

Answer 2

I can't agree with tinstaafl's idea of creating a new array for every input number that starts with a 9. It's not needed in roughly 10% of the possible inputs.

I do however agree that using a for loop is better in this case. Anyone even mildly familiar with for loops can instantly recognise you're looping over each of the digits from right to left which isn't as clear in your while loop.

Instead of breaking the for loop and doing the special case testing afterwards you could also return early instead. With a little bit of rearanging this also simplifies the loop itself slightly.

The final for loop to set the result to all 0's is not needed. Creating a new int[] array will already set them all to 0 for you.

Putting this all together gives us the following implementation:

static int[] plusOne(int[] digits){
    for(int i = digits.length-1; i>=0; i--){
        if(digits[i]<9){
            digits[i]++;
            return digits;
        }
        digits[i]=0; //carry handled by next iteration in for loop
    }
    //didn't return yet so digits were all 9's
    int[] result = new int[digits.length+1];
    result[0] = 1;
    return result;
}

Answer 3

Keep it simple

This condition is used to decide whether an extra digit is needed:

if(a[0]==0)

Why does this work? This works because the only way the first digit is 0, if the digit before that was 9 and there was a carry, which is only possible if the digit before that was 9 and there was a carry, and so on.

This is a lot to keep in the head. There is a much simpler way: declare int carry before the loop, and update it within the loop. The code will look more like this:

int carry = 0;

while (...) {
    // ...
}

if (carry == 1) {

Isn't that a lot simpler to understand and reason about?

Pay attention to style

The computer doesn't care about the writing style, but humans do.

Instead of this:

while(length>=0)
{
    a[length]=a[length]+1;
    int carry = a[length]/10;
    if(carry==1)
    {
        a[length]=0;
        length=length-1;
    }
    else
        break;
}

if(a[0]==0)
{
    int [] array = new int[a.length+1];
    array[0]=1;
    for(int i=1;i<array.length-1;i++)

The preferred writing style in Java is like this:

while (length >= 0) {
    a[length]++;
    int carry = a[length] / 10;
    if (carry == 1) {
        a[length] = 0;
        length--;
    } else {
        break;
    }
}

if (a[0] == 0) {
    int[] array = new int[a.length + 1];
    array[0] = 1;
    for (int i = 1; i < array.length - 1; i++) {

I suggest to follow the above pattern.