Calculate Prize Money - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Addition, Carry Management

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What does the problem ask for?
    • A: The problem asks to add two numbers represented by linked lists where each node contains a single digit in reverse order. The result should also be represented as a linked list in reverse order.
  • Q: What should be returned?
    • A: The function should return the head of a linked list representing the sum of the two numbers.
HAPPY CASE
Input: head_a = Node(2, Node(4, Node(3)))  # 342
       head_b = Node(5, Node(6, Node(4)))  # 465
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807. The result is represented as 7 -> 0 -> 8.

EDGE CASE
Input: head_a = Node(9, Node(9, Node(9)))  # 999
       head_b = Node(1)                    # 1
Output: 0 -> 0 -> 0 -> 1
Explanation: 999 + 1 = 1000. The result is represented as 0 -> 0 -> 0 -> 1.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List problems involving Addition and Carry Management, we want to consider the following approaches:

  • Traversal: Traverse both linked lists simultaneously, adding corresponding digits and managing carry-over.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse both linked lists, adding the corresponding digits along with any carry-over from the previous step. The sum will be stored in a new linked list.

1) Initialize a temporary `head` node to simplify edge cases.
2) Initialize a variable `carry` to `0`.
3) Traverse both linked lists simultaneously:
    a) Add the values of the current nodes and the `carry`.
    b) Create a new `node` with the digit value of `sum % 10`.
    c) Update the `carry` to `sum // 10`.
    d) Move to the next nodes in both lists.
4) If any `carry` remains after traversal, add a new `node` with the `carry` value.
5) Return the next `node` of the temporary `head` (skipping the initial dummy node).

⚠️ Common Mistakes

  • Forgetting to handle cases where the carry remains after processing all nodes.
  • Not correctly managing the addition when one list is longer than the other.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# Function to add two numbers represented as linked lists
def add_two_numbers(prize_a, prize_b):
    temp_head = Node(0)  # Temporary head node to simplify edge cases
    current = temp_head
    carry = 0

    while prize_a or prize_b or carry:
        sum_value = carry

        if prize_a:
            sum_value += prize_a.value
            prize_a = prize_a.next
        
        if prize_b:
            sum_value += prize_b.value
            prize_b = prize_b.next

        # Calculate new carry and the digit to store in the node
        carry = sum_value // 10
        new_node = Node(sum_value % 10)
        current.next = new_node
        current = current.next

    return temp_head.next

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Example: Use the provided head_a and head_b linked lists to verify that the function correctly adds the two numbers.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the longer of the two linked lists.

  • Time Complexity: O(N) because each node is visited exactly once.
  • Space Complexity: O(N) because a new linked list is created to store the result.