Problem

**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

Solution

**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 `int`

s 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; - “10000×9”: 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.