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
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
to9
) - 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
toor
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.