leetcode/add_two_numbers

add_two_numbers

dz / leetcode / add_two_numbers

Summary

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Node Tree

Nodes

URL
content URL
hyperlink https://leetcode.com/problems/add-two-numbers

intuition
content This is mainly a linked list data structure problem. It basically is a problem that tests your ability to work with linked lists. The other half of this problem is understanding base-10 operations. This is a two step operation: Convert each list to an integer value by traversing through the list, then add those values together.
children wait_this_is_bignum (can't convert to integer values because numbers may be quite large), working_through_problem

wait_this_is_bignum
content I just read the constraints, and numbers can be quite large. This instead has to be treated like a bignum data type. The input are two numbers represented as a linked list, and the output is a linked list with the total. The process of adding these is similar to how one would add two long numbers by hand: start at the at the ones place, add the numbers and carry over if needed to the tens, etc. Both the inputs and outputs are in increasing order, so this makes construction of the output easier.
parents intuition

working_through_problem
content Working through the problem steps
children setting_up_iteration
parents intuition

setting_up_iteration
content The loop basically needs to iterate through both lists until they both reach the end. If one reaches before the other, then it is effectively a zero and can be ignored.
children inner_loop
parents working_through_problem

inner_loop
content Inside the loop, we retrieve values from the two lists.
children one_empty, both_empty, both_non_empty
parents setting_up_iteration

both_empty
content If they are both empty, then the output number can be returned.
parents inner_loop

one_empty
content If only one is empty, then take the value and apply any carry-over.
children check_and_set_carry_over (next)
parents inner_loop

both_non_empty
content If both are non-empty, add the two numbers and apply any carry-over. If the value is greater than ten, subtract 10 from the value and set the carry-over flag, otherwise zero it.
children check_and_set_carry_over (next)
parents inner_loop

check_and_set_carry_over
content If the value is greater than 10, subtract from the value, and set the carry-over flag. Otherwise, zero out carry-over.
children append_value (next)
parents one_empty, both_non_empty

append_value
content Append Value to the Output
parents check_and_set_carry_over

cpp_implementation
content Examining the C++ implementation of the solution
children handle_last_carry, modulo_and_division

handle_last_carry
content I forgot to consider handling the last carry flag in my imagining of the solution.
parents cpp_implementation

modulo_and_division
content This implementation uses integer division and modulo operations to figure out the carry flags and extract the value. My approach used conditionals, which I find to be clearer looking code. Relying on the integer division in particular is a little bit too clever for my tastes. There's no branching in this approach, so it's possible this solution produces more efficient code. But it does rely on knowing how arithmetic operations in C++ work. To port this to other languages like python or lua, you'd need to make sure you're using integer operations and not floating point operations.
parents cpp_implementation