Add 1 to an integer represented as an array of digits

Question

Problem Statement

This is another LeetCode question I came across, where I need to add 1 to a number.

The number is represented as an integer array where each index position is a digit and therefore a number from 0-9. There are no leading zeros except for the number 0 itself.
The index position 0, that is arr[0] represents the MSB and the index position n-1, that is
arr[n-1] represents the LSB.

Thus, we need to add one to the LSB and return the number as an integer array. Here is the code which I wrote (it got accepted, passed all test cases) :

class Solution
{
    public int[] plusOne(int[] digits)
    {
        int carry = 0,
        len = digits.length;

        int i = len - 1;

        if (len == 0)
            return digits;

        if (len == 1 && digits[0] < 9)
        {
            digits[0] += 1;
            return digits;
        }

        if (len == 1 && digits[0] == 9)
        {
            digits[0] = 0;
            digits = resize(digits, 2);
            return digits;
        }

        do
        {
            digits[i] += 1;

            if (digits[i] == 10)
            {
                digits[i] = 0;
                carry = 1;
            }
            else
            {
                carry = 0;
                return digits;
            }

            i--;
        } 
        while (carry == 1 && i > -1);

        if (carry == 1)
        {
            digits = resize(digits, len + 1);
            carry = 0;
        }  

        return digits;
    }
    private int[]  resize(int[] arr, int size)
    {
        int[] copy = new int[size];
        int i;

        copy[0] = 1;

        for (i = 1; i < size; i++)
            copy[i] = arr[i-1];

        return copy;
    }
}

Analysis

• Running Time : O(n) in the worst case
• Total Space : O(n) in the worst case
• Worst Case : When adding 1 to a m-digit number results in an (m+1) digit number
  (eg. 999 + 1 = 1000)

Questions

• Is there a better way to solve this problem? (I mean, a different but more efficient algorithm than mine)
  I got a performance of only 29% with this solution no matter how many times I submitted the code, so definitely my algorithm is inefficient
• Instead of using a resizing array, should I be using an array list if I want better performance?
  Can ArrayList handle the overflow condition better than resizing array?
• Should I be using the resizing array technique at all?
  Is it less efficient?
• Is O(n) the best possible running time for the problem?
  I don't see how we can do it O(log n) or less.

Further Notes

• Here is a link to the Github repository which has the above code with more comments: PlusOne.java

Answer 1

Simpler implementation

You can simplify a lot the iteration through the digits. Resizing with an ArrayList would definitely be worse, as it's simply a wrapper of an array and you would need to box/unbox the ints to Integer.

This uses the same algorithm, but with less instructions and it will therefore be a bit faster:

public int[] plusOne(int[] digits) {
  int len = digits.length;
  if (len == 0)
    return digits;

  for (int i = len - 1; i >= 0; i--) {
    if (digits[i] == 9) {
      digits[i] = 0;
    } else {
      digits[i]++;
      return digits;
    }
  }

  return newArray(len + 1);
}

New array

In the case where we create a new array, we know that it will be filled by a 1 followed by all zeros. Since in Java all variables not explicitly initialized have their default values (0 in case of int), we can simply do:

private int[] newArray(int size) {
  int[] arr = new int[size];
  arr[0] = 1;
  return arr;
}

This will save us one read and one write for every position.

Benchmark

I did a test with JMH, comparing both solutions.

Parameters:

# Warmup: 5 iterations, 1 s each
# Measurement: 5 iterations, 1 s each
# Benchmark mode: Average time, time/op

Input data sets:

• "mixed": Starts with {0,0,0,0,0,0,0,0,0,0}, and gets increased in every iteration;
• "10000x9": It's an array composed of 10 000 '9's, like {9, 9, 9, 9, ...}. This is reset back to all-9s in every iteration.

Results:

Benchmark              Mode  Cnt      Score     Error  Units
Test.fill              avgt    5   1852.195 ▒ 101.178  ns/op
Test.new_10000x9       avgt    5   8793.836 ▒ 176.757  ns/op
Test.new_mix           avgt    5      3.957 ▒   0.040  ns/op
Test.original_10000x9  avgt    5  15761.188 ▒  46.132  ns/op
Test.original_mix      avgt    5      4.209 ▒   0.026  ns/op

The fill test case was just to figure out the approximate overhead of resetting the array to 9's in the 10000x9 tests. If we remove that time from the results of the 10000x9 test cases, we see that the new implementation is about twice as fast.