Insert Greatest Common Divisors in Linked List

Medium

Asked by:

43 views

Topics:

Linked Lists

Given the head of a linked list head, in which each node contains an integer value.

Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them.

Return the linked list after insertion.

The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

Example 1:

Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]
Explanation: The 1^st diagram denotes the initial linked list and the 2^nd diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
- We insert the greatest common divisor of 18 and 6 = 6 between the 1^st and the 2^nd nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2^nd and the 3^rd nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3^rd and the 4^th nodes.
There are no more adjacent nodes, so we return the linked list.

Example 2:

Input: head = [7]
Output: [7]
Explanation: The 1^st diagram denotes the initial linked list and the 2^nd diagram denotes the linked list after inserting the new nodes.
There are no pairs of adjacent nodes, so we return the initial linked list.

Constraints:

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

Try coding it in LeetCode

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:

Can the values in the linked list be negative or zero?
What is the maximum size of the linked list, and what is the maximum value of the node data?
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?
If two adjacent nodes have a GCD of 1, should I still insert a node with the value 1?
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:

Start at the beginning of the list.
Look at the first two numbers in the list.
Calculate the greatest common divisor (GCD) of these two numbers.
Insert a new number into the list, between the first and second numbers, and make that new number the GCD you just calculated.
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).
Calculate the GCD of this new pair.
Insert a new number, representing this GCD, between them.
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:

Start at the beginning of the linked list.
Consider the current node and the next node in the list.
Calculate the greatest common divisor (GCD) of the values in these two nodes.
Create a new node with this GCD as its value.
Insert this new node immediately after the current node.
Move to the next original node in the linked list (skipping the node you just added).
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

Case	How to Handle
Empty linked list	Return null immediately if the input linked list is empty.
Linked list with only one node	Return the original list, as no GCD can be inserted between a single node.
Linked list with two nodes where GCD is 1	Ensure the solution correctly inserts a node with value 1 between the two nodes.
Linked list with two nodes where the numbers are equal	The 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 calculation	Use a GCD algorithm that avoids overflow by using subtraction/modulo operations rather than multiplication.
Linked list contains nodes with values of zero	The 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 implementations	Use an iterative GCD algorithm to avoid potential stack overflow errors with deep recursion.
Memory constraints when creating many new nodes in very large lists	Ensure efficient memory allocation when inserting new nodes to avoid memory exhaustion issues.

Empty linked list

How to Handle:

Return null immediately if the input linked list is empty.

Linked list with only one node

How to Handle:

Return the original list, as no GCD can be inserted between a single node.

Linked list with two nodes where GCD is 1

How to Handle:

Ensure the solution correctly inserts a node with value 1 between the two nodes.

Linked list with two nodes where the numbers are equal

How to Handle:

The 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 calculation

How to Handle:

Use a GCD algorithm that avoids overflow by using subtraction/modulo operations rather than multiplication.

Linked list contains nodes with values of zero

How to Handle:

The 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 implementations

How to Handle:

Use an iterative GCD algorithm to avoid potential stack overflow errors with deep recursion.

Memory constraints when creating many new nodes in very large lists

How to Handle:

Ensure efficient memory allocation when inserting new nodes to avoid memory exhaustion issues.