3
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ One improvement: there's no need to pass the old digits arr to the resize() method. \$\endgroup\$ – Ralf Kleberhoff Nov 10 '17 at 13:09
  • \$\begingroup\$ thanks, I fixed it. In fact resize is now misleading, I renamed it. \$\endgroup\$ – Duarte Meneses Nov 10 '17 at 13:45
  • 3
    \$\begingroup\$ @DuarteMeneses thanks so much for the enlightenment! While your code also performed at around 30% on LeetCode (which is not a matter of concern in any way), what I loved about your solution was it's simplicity and elegance. The way you showed me how to modify the array length by avoiding unnecessary read/write was truly awesome! Thank you so much! :) \$\endgroup\$ – enigma6174 Nov 10 '17 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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