Improvement of the time complexity of "incrementing a number represented as an array of digits"
Problem Given a non-negative number represented as an array of digits,
add 1 to the number (increase the number indicated by numbers).
The numbers are stored so that the most significant digit is at the top of the list.
Example:
If the vector has [1, 2, 3]
the returned vector must 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]
Ok I am getting the correct answer. However, I am not satisfied with the complexity of the code time. Suggestions for improving this code would be appreciated.
source to share
The complexity of your method is O (n) and you can't do better in terms of great complexity in the worst case.
Difficulty changing is not the only thing that matters. The Big-o note does not account for multiplicative and additive constants, this does not mean that such constants do not affect the performance of your algorithm. For example, in your code, you are doing 2 O (n) loops. In the first loop, you do some arithmetic operations, and in the second, you use append
, which amortized the worst case O (1), but which (referring to the docs):
[...] rely on the "amortized" part of the "Amortized worst case". Individual actions can take a surprisingly long time, depending on the history of the container.
You can do the same operations with smaller constants (I think). For example:
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) times in the worst case (all 9s). On average, however, the loop takes less than O (n). When we break out of the worst case loop, we need to insert an element at the beginning of the list that has unamortised O (n) complexity.
On average, this approach should be faster, but it doesn't change the worst-case O (n) complexity.
source to share
You cannot improve the time complexity O(n)
because if the input file is all 9, then you need to change n
nines to zero and add it at the beginning:
def increment(digits):
for i in reversed(range(len(digits))):
if digits[i] != 9:
digits[i] += 1
break
else:
digits[i] = 0
else: # no break, all 9s
digits.insert(0, 1) #
Example:
>>> a = [1, 2, 3]
>>> increment(a)
>>> a
[1, 2, 4]
The array grows in case of "only 9s":
>>> a = [9, 9, 9]
>>> increment(a)
>>> a
[1, 0, 0, 0]
source to share