# Add 1 to an integer represented as an array of digits

Posted on

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 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 < 9)
{
digits += 1;
return digits;
}

if (len == 1 && digits == 9)
{
digits = 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 = 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 = 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.