Add one to integer represented as an array

Question

I am practicing interview questions and have written the following code for the given task.

Task : 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.

Code:

class Solution:
# @param A : list of integers
# @return a list of integers
 def plusOne(self, A):
 Rev_A = A[::-1]
 i = 0
 while i <= len(A)-1:
 if Rev_A[i] != 9:
 Rev_A[i] +=1
 carry = 0
 break
 else:
 Rev_A[i] = 0
 carry = 1
 i += 1
 if carry == 1:
 Rev_A.append(1)
 while True:
 if Rev_A[-1]==0:
 Rev_A.pop()
 else:
 break
 return Rev_A[::-1]
 def __init__(self):
 self.list = []

Test cases:

if __name__ == "__main__":
 A = Solution()
 ## Test Cases 
 print A.plusOne([0])
 print A.plusOne([9,0,0])
 print A.plusOne([6,9,9])
 print A.plusOne([9,9,9])
 print A.plusOne([0,9,9,9])
 print A.plusOne([0,0,0,1,2,3])

How can this code be better?

• Latika Agarwal: @Ohh thats a mistake while adding the test cases. I will edit it

Answer 1

1. Run the code through pycodestyle, then understand and apply all of the recommended changes. This is tedious the first couple times, but you'll learn to write much more idiomatic Python.
2. The class is pointless - you might as well just write a bare function instead. __init__ also creates a field which is then never used.
3. Names like A make the code harder to read. Naming your variables what they actually are makes the code much easier to read.
4. I would swap around your first if/else to avoid the negative comparison.
5. You use a number for carry, but it might as well be boolean because it can never be more than 1.

6. Personally I consider this code hard to understand. You reverse the list twice (making a copy both times), add and remove to it. This is my take on it:

   def increment(digits):
    for index, digit in reversed(list(enumerate(digits))):
    if digit == 9:
    digits[index] = 0
    else:
    digits[index] += 1
    return digits
    digits.insert(0, 1)
    return digits
   if __name__ == '__main__':
    print(increment([0]))
    print(increment([9,0,0]))
    print(increment([6,9,9]))
    print(increment([9,9,9]))
    print(increment([0,9,9,9]))
    print(increment([0,0,0,1,2,3]))
   

   1. Reverse the list one element at a time
   2. Set trailing nines to zero
   3. If any number is not nine, increment it and we're done
   4. If we get through the whole list, it must have been all nines, so we add a one to the start and return
   5. This code treats an empty list as zero, which may or may not be allowed in the exercise.

• Latika Agarwal: Thanks for your review. The class function was inbuilt with the console i was practising on, so i had to use. Yes, reversing the list twice was really inefficient..
• njzk2: Nice simplification of the increment algorithm! However you are both mutating and returning digit. I would recommend picking one. (and optionally renaming the function accordingly, like incremented if you choose to return a new list)
• njzk2: also, you don't necessarily need to create a list out of the enumerate (as that adds an expensive step right before starting to even loop). An alternative option would be to use for index in range(len(digits) -1, -1, -1) and then if digits[index] == 9...

Answer 2

1. This while loop:

i = 0
while i <= len(A) - 1:
 ...
 i += 1

should just be a for loop:

for i in range(len(A)):
 ...

or:

for i, x in enumerate(A): # x == A[i]
 ...

2. Building on l0b0's suggestions 4 and 5:

carry = Rev_A[i] == 9 # or x == 9
if carry:
 Rev_A[i] = 0
else:
 Rev_A[i] += 1
 break

3. This:

while True:
 if Rev_A[-1] == 0:
 Rev_A.pop()
 else:
 break

can be:

while Rev_A[-1] == 0:
 Rev_A.pop()

4. The purpose of the above loop isn't clear. If the input has extra zeroes, why not let them be? You're doing something outside of the scope of the task, which takes time and increases the chances of errors, and which the user may not what. Maybe I want my 'numbers' to be sortable lexicographically.

5. Descriptive variable names are good, but here you have so few and you repeat Rev_A so many times. Rather I would make both A and Rev_A just a. That includes writing a = a[::-1]. The reader will quickly learn what a is and doesn't need a long name to remind them.

6. Write actual test cases that assert the output of the function is equal to something. Never require manual inspection of output to determine if tests passed.

7. You've written comments instead of a docstring. Don't. Also describe parameters and return values more than just their types.

• Latika Agarwal: Thanks for your review. The extra zeroes were part of the input but had to be removed in the o/p. It was a variation in the test cases.

Answer 3

The problem is well suited for recursion. I don't know if it is wise in an interview to metion quotes as: "to iterate is human, to recurse is divine" but recursion is a fun approach for this problem.

As l0b0 said a class is not needed for this case so i changed the method plusOne to a normal function.

def plusOne(a):
 return addOneToDigitsList(a, 1)

Where addOneToDigitsList is the following recursive function:

def addOneToDigitsList(a, pos):
 if pos > len(a):
 a.insert(0,0)
 if a[-pos] != 9:
 a[-pos] += 1
 return a
 else:
 a[-pos] = 0
 return addOneToDigitsList(a, pos + 1)

The remaining part is almost the same:

def main():
 ## Test Cases 
 print(plusOne([0]))
 print(plusOne([9,0,0]))
 print(plusOne([6,9,9]))
 print(plusOne([9,9,9]))
 print(plusOne([0,9,9,9]))
 print(plusOne([0,0,0,1,2,3]))
if __name__ == "__main__":
 main()

• I added a main function because it is common to do so
• I added parentheses to make it Python 3 compatible
• I did not, but should have, used Alex Hall comments about docstrings.
• I should have done more error checking (for unexpected situations)