Leetcode 2. Add Two Numbers - my solution
Tags: python, leetcode
Published: 2023-07-03 17:36:22

## Description
- 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.
```
**Input:** l1 = [2,4,3], l2 = [5,6,4]
**Output:** [7,0,8]
**Explanation:** 342 + 465 = 807.
```

- **Constraints:**
- The number of nodes in each linked list is in the range `[1, 100]`.
- `0 <= Node.val <= 9`
- It is guaranteed that the list represents a number that does not have leading zeros.

## Problem definition
- Function:add two numbers
- Input: list1, a linked list, list2, a linked list
- Precondition: 0<|list1| < 100, |list 2| > 0, 0 ≤ node.value ≤ 9, 0< list1[0]  ≤ 9, 0< list2[0]  ≤ 9
- Output: sum, a linked list
- Postcondition: 
{% katex inline %} sum[0] \times 10^0 + sum[1] x 10^1  ... + sum[| sum | - 1] \times 10^{| list1 | - 1} = list1[0] x 10^0 + list1[1] \times 10^1  ... + list1[| list1 | - 1] \times 10^{| list1 | - 1} + list2[0] \times 10^0 + list2[1] \times 10^1  ... + list2[| list2 | - 1] x 10^{| list2 | - 1} {% endkatex %}   

## The outline of the algorithm
- This question can be divided into two parts: 1. calculate the sum of the two linked lists and 2. convert the sum into a linked list.
-  I solve this in a recursive style

### The first part
- Function: sum of a list
- Input: list1, a linked list, degree, an integer
- Precondition: 0 < |list1| < 100,  0 ≤ node.value ≤ 9,  0< list1[0] ≤ 9 
- Output: sum, an integer
- Postcondition: {% katex inline %} sum = list1[0] \times 10^{degree}  + list1[1] \times 10^{degree + 1}  ... + list1[| list1 | - 1] \times 10^{degree + | list1 |} {% endkatex %}   

---
-  Let's think about the base case: The lowest possible input is there is only one node in the linked list, which means its next value is None. In this case, we multiply the value of the current pointing node by 10 to the power of nodes we travel
- What about other cases: we multiply the value of the current pointing node by 10 to the power of nodes we travel, I use **degree** to denote it and + call the function on the next node

---
- The recursive definition  is:
	- if n is the last node: node.value x {% katex inline %} 10^{degree} {% endkatex %}  
	- otherwise: node.value x {% katex inline %} 10^{degree} {% endkatex %}  + sum of a list(node.value, degree + 1).  

---
- For the complexity, in each recursive call, we calculate the node.value x 10^{degree}  which has a complexity of O(\log  degree)
- number of recursive call x complexity of each call = {% katex inline %}( | list1 | \times O(\log  degree)) = O ( | list1 | \times \log  degree) {% endkatex %}  . Since the degree is increased by 1 for everyone more linked list, so it is also {% katex inline %}O(\log  |list1|) {% endkatex %}  .
- The code
```python
def sum_of_a_list(node, degree = 0):
        if node.next == None:
            return node.val * 10 ** degree
        else:
            return node.val * 10 ** degree + sum_of_a_list(node.next, degree + 1)
```

### The second part
- this part is to create a linked list from the sum of the two linked list
- Function: new linked list
- Input: sum, an integer
- Precondition: an int ≥ 0
- Output:  list3, a linked list
- Postcondition: {% katex inline %}  sum = list3[0] \times 10^{0}  + list3[1] \times 10^{1}  ... + list3[| list3 | - 1] \times 10^{| list3 |} {% endkatex %}


#### The outline of the algorithm
- I would assign one digit to one node starting from the last digit of the **sum**, the last digit can be found by the remainder *sum* divided by 10. Every time I assign a digit, I will shift the end pointer to the left by shortening the **sum** using floor division by 10. Since in this implementation, there is no head pointer to the first node of the linked list, I have to explicitly create a **first node** variable to assign the last digit of the *sum* and pass the rest of **sum** to the recursive function.

---
- The base case of the reclusive approach would be the sum becoming 0. The **sum** will only become 0 when both linked lists have only a 0 value node or after the floor division a single digit, which means the last digit of the sum. The former situation is handled by the creation of the **first node** variable. In the latter situation, since there is no leading 0 in the **sum**, so we don't need to assign this 0, so we will assign the value of this node to be None.
- In other cases: we assign the last digit of the **sum** and then cut the last digit of the **sum** and assign the node.next value to the next node
- The recursive definition is:
	- if sum = 0: node.val = none
	- if sum > 0: 
		- current node.val = sum % 10
		- sum = sum // 10
		- current node.next = new linked list(sum)

---
- The complexity is basically affected by the number of digits of **sum**, i.e. {% katex inline %} O((\log_{10} sum) + 1) = O (\log sum){% endkatex %}. Since **sum** is larger when the two linked list given in the first place is longer, so this also mean it has a complexity of O(log l list1|).  
- The code
```python
def new_linked_list(sum:int):
  def in_new_linked_list(an_int2:int):
            if an_int2 == 0:
                return None
            else:
                current_node = ListNode()
                current_node.val = an_int2 % 10
                an_int2 = an_int2 // 10
                current_node.next = in_new_linked_list(an_int2)
                return current_node
          
        first_node = ListNode(sum % 10)
        sum = sum // 10
        first_node.next = in_new_linked_list(sum)
        return first_node 
```

## Combined algorithm
1. let **sum** be the sum of list1 and the sum of list 2
2. convert **sum** to a linked list
3. let **first node** be the linked list of **sum**

- The overall complexity is {% katex inline %}  O (( | list1 | \times \log  | list1 |) + \log | list1 | ){% endkatex %} = O (( | list1 | x \log  | list1 |). Since we are concerned only with the fastest growing term. This means the overall complexity is a log-linear complexity.
- The Code
```python
def addTwoNumbers(l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """
    def sum_of_a_list(node, degree = 0):
        if node.next == None:
            return node.val * 10 ** degree
        else:
            return node.val * 10 ** degree + sum_of_a_list(node.next, degree + 1)

    # degree = 0
    sum = sum_of_a_list(l1,0) + sum_of_a_list(l2, 0)

    def new_linked_list(sum:int):
        def in_new_linked_list(an_int2:int):
            if an_int2 == 0:
                return None
            else:
                current_node = ListNode()
                current_node.val = an_int2 % 10
                an_int2 = an_int2 // 10
                current_node.next = in_new_linked_list(an_int2)
                return current_node
            
        first_node = ListNode(sum % 10)
        sum = sum // 10
        first_node.next = in_new_linked_list(sum)
        return first_node   
    
    return new_linked_list(sum)
```

## Feeling

![The ranking of completing leetcode 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6801ryg4nfik0sv15k1k.png)
- - Actually, I am quite happy to finish this challenge, although this is a slow algorithm. This is the first time, I successfully write a recursive algorithm outside of the course material. This give me more confidence and experience to write recursive algorithms which I am a bit confused about before.

## Reference:
[Add Two Numbers - LeetCode](https://leetcode.com/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-100-liked)