Improving Time Complexity of "increment the number represented as an array of digits"

Question

Problem Given a non-negative number represented as an array of digits,

add 1 to the number ( increment the number represented by the digits ).

The digits are stored such that the most significant digit is at the head of the list.

Example:

If the vector has [1, 2, 3]

the returned vector should be [1, 2, 4]

as 123 + 1 = 124.

My Code

def plusOne(A):
    num = 0

    for digit in A:
        num = num*10 + digit

    retnum = num + 1

    retA = []

    while retnum > 0:
        retA.append(retnum % 10)
        retnum /= 10

    return retA[::-1]

Well, I am getting the correct answer by this. However, I am not satisfied by the code's time complexity. Suggestions for improving this code will be appreciated.

Answer 1

The complexity of your method is O(n) and you cannot do better in terms of big-o complexity in the worst case.

Changing the big-o complexity is not the only thing that matters however. Big-o notation does not take into account multiplicative and additive constants, this does not mean that such constants do not affect the performance of your algorithm. In your code, for instance, you are performing 2 O(n) cycles. In the first loop you do some arithmetic operations while in the second one you use append which has amortized worst case O(1) but that (citing from the docs):

[...] rely on the "Amortized" part of "Amortized Worst Case". Individual actions may take surprisingly long, depending on the history of the container.

You could perform the same operations in place with (I think) smaller constants. For instance:

i = len(A) - 1

while i >= 0 and A[i]==9:
  A[i]=0
  i=i-1

if i >= 0:
  A[i] = A[i]+1
else:
  A.insert(0,1)

The first loop takes O(n) time in the worst case (all 9s). In the average case, however, the loop takes less than O(n). When we exit the loop in the worst case we need to insert an element at the beginning of the list which has non-amortized O(n) complexity.

In the average case this approach should be faster, but it does not change the worst case O(n) complexity.