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?

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.

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.

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)