Problem Solving Skills: Add Two Numbers

My thinking process to solve the Add Two Numbers problem

When I first solve this problem, I felt it could be a good example to show the importance of really understand the problem before you solve it.

Actually it is not a tough problem. The key is to ask good questions, figure out the corner cases and create examples to better understand it.

Add Two Numbers Problem

Add Two Numbers

You can access the link above if you want to see the description and its examples.

1. Understand the problem. Ask questions.

The first step is to read the problem description. It seems silly but people just read the key points and sometimes don’t read really important info to handle corner cases.

When I read the problem description some questions were popping into my head. But before we can ask anything, let’s read the description info. We have:

• 2 non negative integers linked lists
• Both linked lists contain at least 1 element (non-empty)
• Each node stores a single digit (numbers from zero to 9)
• We need to sum each node and return a new linked list
• We need to handle carry
• We don’t know if those lists can have different sizes. And they can. Actually I needed to test it to know. This is an example of question you can ask the interviewer to clarify the problem

2. Creating examples to better understand the problem

Creating example not just help you understand the problem but also figure out some corner cases you don’t expect.

Going crazy here help us build our algorithm to handle all corner cases. And when I say crazy I mean very different examples: from basics and obvious to non-trivial examples.

• The basic and most obvious example:

(1, 2, 3) + (2, 3, 4) = (3, 5, 7)

We don’t need to handle the carry, just simple sums.

• Handle simple carry:

(1, 2, 3) + (2, 9, 4) = (3, 1, 8)

Here we have a simple carry, not multiple carry to handle and same number nodes for both lists.

• Handle carry for last node

(5) + (5) = (0, 1)

If we need to handle carry for last digit, we just add 1 as the new list last node.

• Lists with different number of nodes

(3, 6) + (1, 7, 5) = (4, 3, 6)

Here we have the most complex example: handle carry and different number of nodes.

3. Brute force solution for the simplest example

• Lists with same number of nodes
• We don’t need to cover carry

First the problem gives us the ListNode class. This is how we can use it:

val is the digit stored in our node. And next is the next node the current node is pointing to.

We receive l1 and l2 as the two lists’ nodes. And need to return a new list.

For the first and simplest solution:

• We just need to iterate through both lists
• Sum each node value
• Create a new list with the added value
• Setting the new list node to the current node’s next attribute
• Updating the current node

Algorithm implementation done! Let’s test it!

• Create the first list: (1, 2, 3)

• Create the second list: (2, 2, 4)

• Call the add_two_numbers function

• Print the new list’s nodes to see if it’s correct:

• Result: (3, 4, 7)

4. Algorithm Improvements: handle carry

In elementary arithmetic, a carry is a digit that is transferred from one column of digits to another column of more significant digits. — Wikipedia

The first thing that came to my mind is using a boolean value to manage the carry. So it would start with a False value and when the sum of node values is greater or equal to 10 I would update it with True value, to use it in the next digit (use: add +1 to the digit).

Another we need to manage is the sum of both nodes’ values. For example:

• List Node 1: value 7
• List Node 2: value 9

When we update the carry to True value, we also update the sum value, decreasing it by 10. Why? 7 + 9 = 16. Decreasing it by 10 equals to 6.

6 is the value of the next node we need to create. And we user the carry in for next node value. Let’s test it!

Result: (1, 2, 3) + (2, 9, 4) = (3, 1, 8)

Carry happens when we sum 2 + 9 and increase the sum of 3 + 4 by 1 (8).

5. Algorithm Improvements: cover carry for last sum

To manage the carry on the last digit of lists’ node, we just need to make a little improvement on our algorithm: an else statement.

When the carry is on the last digit, l1 and l2 are None and will the if will evaluates to False. Using the else statement we can control the value variable setting it to 0 (zero). Then we handle the carry increment the value by 1.

That’s it, we have the new last node with value 1.

6. Algorithm Improvements: cover different number of nodes

The last improvements we need to make for our algorithm is to cover different number of nodes. We do it just:

• Changing the and to or on out while statement
• Adding elif statements to handle different number of nodes

That’s it! We cover all the corner cases :)

That’s it!

If you want to see the complete file with the algorithm, examples and tests, access here. If you have doubts about Python syntax/concepts, and want to learn it, here is an awesome post about Learning Python from Zero to Hero.

This is a simple and easy problem to solve, but I learnt how to ask good questions and make examples to better understand and solve it. Hope you learnt it too!

From more stories and posts about my journey learning & mastering algorithms and data structures, follow my publication The Renaissance Developer.

Have fun, keep learning & always coding!

My Twitter & Github. ☺