Taro Logo

Insert Greatest Common Divisors in Linked List

Medium
Google logo
Google
1 view
Topics:
Linked Lists

Given the head of a singly linked list head, where each node contains an integer value, your task is to insert a new node between every pair of adjacent nodes. The value of this new node should be equal to the greatest common divisor (GCD) of the two adjacent nodes.

Return the modified linked list after the insertions. The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

For example, consider the linked list: 18 -> 6 -> 10 -> 3. You should modify this list as follows:

  1. Calculate the GCD of 18 and 6, which is 6. Insert a new node with the value 6 between 18 and 6. The list becomes: 18 -> 6 -> 6 -> 10 -> 3.
  2. Calculate the GCD of 6 and 10, which is 2. Insert a new node with the value 2 between 6 and 10. The list becomes: 18 -> 6 -> 6 -> 2 -> 10 -> 3.
  3. Calculate the GCD of 10 and 3, which is 1. Insert a new node with the value 1 between 10 and 3. The list becomes: 18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3.

Another example, given the linked list: 7

Since there are no adjacent pairs, you should return the original linked list: 7

Constraints:

  • The number of nodes in the list is in the range [1, 5000].
  • 1 <= Node.val <= 1000

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Can the values in the linked list be negative or zero?
  2. What is the maximum size of the linked list, and what is the maximum value of the node data?
  3. If the input list is empty or contains only one node, what should the function return? Should it return null, the original list, or raise an exception?
  4. If two adjacent nodes have a GCD of 1, should I still insert a node with the value 1?
  5. Is it acceptable to modify the existing linked list, or should I create a new one?

Brute Force Solution

Approach

The brute force approach to inserting greatest common divisors (GCDs) into a linked list means we will examine every consecutive pair of numbers in the list. For each pair, we'll compute their GCD and insert it between them. We will repeat this process until we've gone through the entire list.

Here's how the algorithm would work step-by-step:

  1. Start at the beginning of the list.
  2. Look at the first two numbers in the list.
  3. Calculate the greatest common divisor (GCD) of these two numbers.
  4. Insert a new number into the list, between the first and second numbers, and make that new number the GCD you just calculated.
  5. Move to the next pair of numbers in the list (the second number and the number that comes after it, which might be the GCD we just inserted).
  6. Calculate the GCD of this new pair.
  7. Insert a new number, representing this GCD, between them.
  8. Keep repeating these steps until you reach the end of the list.

Code Implementation

def insert_greatest_common_divisors(head):
    current_node = head

    while current_node and current_node.next:
        first_value = current_node.val
        second_value = current_node.next.val

        # Calculate the GCD of the two consecutive values
        greatest_common_divisor = calculate_gcd(first_value, second_value)

        # Create a new node with the GCD
        gcd_node = ListNode(greatest_common_divisor)

        # Insert the new node between the current and next node
        gcd_node.next = current_node.next
        current_node.next = gcd_node

        # Move to the node after the inserted GCD node
        current_node = gcd_node.next

    return head

def calculate_gcd(first_number, second_number):
    while(second_number):
        first_number, second_number = second_number, first_number % second_number
    return first_number

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def insert_greatest_common_divisors_brute_force(head):
    current_node = head

    while current_node and current_node.next:
        # Store values for easier use
        first_value = current_node.val
        second_value = current_node.next.val

        # Calculate the GCD of these two numbers
        greatest_common_divisor = calculate_gcd(first_value, second_value)

        # Create a new node for the GCD
        gcd_node = ListNode(greatest_common_divisor)

        # Insert the GCD node
        gcd_node.next = current_node.next
        current_node.next = gcd_node

        #Move to the next pair (original next and the new next)
        current_node = gcd_node.next

    return head

Big(O) Analysis

Time Complexity
O(n log(max_val))We iterate through the linked list of n nodes. In each iteration, we calculate the GCD of two adjacent nodes. The GCD calculation typically involves the Euclidean algorithm, which takes O(log(min(a, b))) time, where a and b are the two numbers. In the worst case, a and b can be up to max_val and the GCD operation will be bounded by O(log(max_val)). Thus, we perform O(log(max_val)) operation n times, resulting in a time complexity of O(n log(max_val)).
Space Complexity
O(1)The algorithm iteratively computes the GCD of consecutive pairs and inserts new nodes. The only extra space needed is for a few temporary variables to store the GCD and potentially a pointer to the new node being inserted. The number of extra variables does not depend on the length of the linked list (N). Therefore, the space complexity is constant.

Optimal Solution

Approach

The goal is to go through the linked list and insert new nodes with the greatest common divisor (GCD) between consecutive nodes. We can do this efficiently by traversing the list once, computing the GCD on the fly, and inserting a new node after each original node.

Here's how the algorithm would work step-by-step:

  1. Start at the beginning of the linked list.
  2. Consider the current node and the next node in the list.
  3. Calculate the greatest common divisor (GCD) of the values in these two nodes.
  4. Create a new node with this GCD as its value.
  5. Insert this new node immediately after the current node.
  6. Move to the next original node in the linked list (skipping the node you just added).
  7. Repeat steps 2-6 until you reach the end of the linked list.

Code Implementation

def insert_greatest_common_divisors(head):
    current_node = head

    while current_node and current_node.next:
        # Calculate GCD between current and next node value
        gcd_value = calculate_gcd(current_node.val, current_node.next.val)

        # Create a new node for the GCD.
        gcd_node = ListNode(gcd_value)

        gcd_node.next = current_node.next
        current_node.next = gcd_node

        # Move to the next original node.
        current_node = gcd_node.next

    return head

def calculate_gcd(first_number, second_number):
    while second_number:
        first_number, second_number = second_number, first_number % second_number
    return first_number

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Big(O) Analysis

Time Complexity
O(n)We iterate through the linked list once, where n is the number of nodes in the list. For each node, we calculate the GCD with the next node and insert a new node. The GCD calculation itself takes O(log(min(a,b))) time, where a and b are the values of the two nodes, but this is independent of n and can be considered constant. Therefore, the dominant factor is the single pass through the list, resulting in O(n) time complexity since we perform a constant amount of work for each of the n nodes.
Space Complexity
O(1)The algorithm iterates through the linked list and inserts new nodes containing the GCD. The GCD calculation itself uses constant space. The insertion process creates new nodes, but this is considered part of the output and not auxiliary space. Therefore, only a few variables for the current node and the next node are needed, making the auxiliary space constant, regardless of the linked list's size N.

Edge Cases

CaseHow to Handle
Empty linked listReturn null immediately if the input linked list is empty.
Linked list with only one nodeReturn the original list, as no GCD can be inserted between a single node.
Linked list with two nodes where GCD is 1Ensure the solution correctly inserts a node with value 1 between the two nodes.
Linked list with two nodes where the numbers are equalThe GCD will be the value of the node; ensure that value is inserted correctly.
Large numbers in the linked list nodes that could cause integer overflow during GCD calculationUse a GCD algorithm that avoids overflow by using subtraction/modulo operations rather than multiplication.
Linked list contains nodes with values of zeroThe GCD of zero and any number is the number; ensure the calculation handles this case gracefully and correctly.
Very long linked list to ensure there's no stack overflow in recursive GCD implementationsUse an iterative GCD algorithm to avoid potential stack overflow errors with deep recursion.
Memory constraints when creating many new nodes in very large listsEnsure efficient memory allocation when inserting new nodes to avoid memory exhaustion issues.