2807. Insert Greatest Common Divisors in Linked List

Problem Description

The problem requires us to modify a given singly linked list by inserting new nodes. Specifically, for every two adjacent nodes in the list, we need to insert a new node between them. The value of this new node is not just any number but the greatest common divisor (GCD) of the values of these two adjacent nodes. The GCD of two numbers is the largest number that divides both of them without leaving a remainder.

For example, if our linked list is 1 -> 4 -> 3 -> 8, then after inserting new nodes, it should look like 1 -> 1 -> 4 -> 1 -> 3 -> 1 -> 8, where the numbers 1, 1, and 1 are the GCDs of 1 and 4, 4 and 3, 3 and 8 respectively. Note that if the GCD is 1, it means that the two numbers are coprime (they have no common divisor other than 1).

Intuition

For solving this problem, we need to traverse the linked list and calculate the GCD of every two adjacent values. We do not need any extra space besides the new nodes that we are inserting, and we can do the insertion in a single pass through the list.

The steps involve:

Start by pointing to the first node of the list.
While we have not reached the end of the list (i.e., the current node's next is not None):
- Calculate the GCD of the current node's value and the next node's value.
- Create a new node with the calculated GCD value.
- Insert this new node between the current node and the next node.
- Move to the next pair of nodes to continue the process.

We use a utility function, gcd, which will calculate the greatest common divisor of two numbers. Python provides a built-in function for this in the [math](/problems/math-basics) module, which could be employed to simplify our code. The process of inserting the new node involves manipulating the next pointers of the nodes to accommodate the new GCD node in between.

Overall, this approach works because linked lists allow for efficient insertion operations since, unlike arrays, we do not need to shift elements after the insertion point. We can simply rewire the next pointers appropriately to complete the insertion.

Learn more about Linked List and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Generating subsetsGenerating random numbersGenerating permutationsSorting integers

Solution Approach

The solution involves manipulation of linked list nodes and calculating the greatest common divisor (GCD) between adjacent nodes. The steps below detail the algorithm used in the provided code:

Initialization: We initialize two pointers, pre and cur. The pre holds the reference to the current node, where we will insert a new node after, and cur holds the reference to the next node, which will be used for calculating GCD. Initially, pre points to head and cur points to head.next.
Traversal and Insertion:
- We enter a loop that continues to iterate as long as cur is not None, meaning there are still nodes to process.
- Inside the loop, we calculate the GCD of pre.val and cur.val using a function gcd. This function is assumed to be predefined or imported from the [math](/problems/math-basics) module in Python (from math import gcd).
- We create a new ListNode with the calculated GCD, and its next points to cur. This effectively creates a new node between pre and cur.
- Next, we rewire the next pointer of the pre node to point to the new node.
- We update the pre pointer to now point to the cur node, since we've finished inserting the new node after what pre was pointing to before.
- Lastly, we update cur to point to cur.next, moving forward in the linked list to the next pair of nodes.
Algorithm Pattern: The approach here doesn't use extra space for an auxiliary data structure but directly works on the list itself, modifying pointers as needed. It's an in-place algorithm with respect to linked list manipulation, although new nodes are created for storing the GCDs.
GCD Function: The GCD function utilized is a key part of this solution, which calculates the greatest common divisor of two given numbers. If Python's built-in gcd function is not being used, an implementation of the Euclidean algorithm would typically be employed.

This implementation's time complexity is O(n * log(max(A))), where n is the number of nodes in the list and log(max(A)) represents the time complexity of computing the GCD for any two numbers in the list (assuming A is the set of integers in the nodes). The space complexity is O(1) ignoring the space taken by the output list; in a more practical sense, considering the new nodes, it would be O(n) due to the new nodes being inserted into the linked list.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Example Walkthrough

Let us consider a small linked list: 5 -> 10. According to the problem, we need to find the GCD of every two adjacent nodes and insert a new node with that value in between them. In this case, we only need to find the GCD of 5 and 10. Using the Euclidean algorithm, we see that the GCD of 5 and 10 is 5.

Here is the step-by-step process based on the solution approach:

Initialization: We begin with two pointers, pre is pointing to the node with value 5 (head of the list), and cur is pointing to the node with value 10 (head.next).
Traversal and Insertion:
- Since cur is not None, we enter the loop.
- We compute the GCD of pre.val (5) and cur.val (10), which is 5.
- A new node is created with the GCD value 5, and its next is set to point to cur (ListNode(5, cur)).
- We then update pre.next to point to this new node. The linked list now looks like 5 -> 5 -> 10.
- We move pre to point to cur, which is the node with the value 10.
- cur is updated to cur.next, which is None (end of the list).

By end of these steps, the traversal and insertion phase is complete, as there are no more nodes to process. The final linked list after the GCD insertion is 5 -> 5 -> 10. It must be noted that if the linked list were longer, we would continue the process until we reach the end of the list.

Algorithm Pattern: In our example, we traversed the list and inserted the nodes without any extra data structures or modification of the original nodes' values. We only changed the next pointers to accommodate the new nodes.
GCD Function: The GCD value was calculated using the known algorithm, or we could have used Python's built-in gcd function for simplification (from math import gcd).

This example demonstrates the workings of our approach on a very small linked list. For linked lists with more nodes, the method would continue analogously until every pair of adjacent nodes has been processed.

Solution Implementation

1from math import gcd
2
3# Definition for singly-linked list.
4class ListNode:
5    def __init__(self, val=0, next_node=None):
6        self.val = val
7        self.next = next_node
8
9class Solution:
10    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
11        # Initialize pointers: 'prev_node' pointing to the current node being processed, 
12        # and 'current_node' pointing to the next node in the list.
13        prev_node, current_node = head, head.next
14      
15        # Iterate through the linked list until we reach the end.
16        while current_node:
17            # Compute Greatest Common Divisor (GCD) of the values in the 'prev_node' and 'current_node'.
18            gcd_value = gcd(prev_node.val, current_node.val)
19          
20            # Insert a new node with the GCD value between the 'prev_node' and 'current_node'.
21            prev_node.next = ListNode(gcd_value, current_node)
22          
23            # Update pointers: move 'prev_node' to the 'current_node' and
24            # 'current_node' to the next node in the list.
25            prev_node, current_node = current_node, current_node.next
26      
27        # Return the modified linked list head.
28        return head
29

1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    int val;
6    ListNode next;
7    ListNode() {}
8    ListNode(int val) { this.val = val; }
9    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
10}
11
12public class Solution {
13
14    /**
15     * Inserts a new node with the value of the greatest common divisor 
16     * between each pair of adjacent nodes in the linked list.
17     *
18     * @param head The head of the singly-linked list.
19     * @return The head of the modified linked list, with new nodes added.
20     */
21    public ListNode insertGreatestCommonDivisors(ListNode head) {
22        // Initialize two pointers for traversing the link list.
23        ListNode prev = head;
24        ListNode curr = head.next;
25
26        // Iterate over the list until we reach the end.
27        while (curr != null) {
28            // Get the greatest common divisor of the values in the two nodes.
29            int gcdValue = gcd(prev.val, curr.val);
30
31            // Insert a new node with the GCD value between the two nodes.
32            prev.next = new ListNode(gcdValue, curr);
33
34            // Move the pointers forward to the next pair of nodes.
35            prev = curr;
36            curr = curr.next;
37        }
38
39        // Return the unchanged head of the modified list.
40        return head;
41    }
42
43    /**
44     * Helper function to calculate the greatest common divisor of two integers.
45     *
46     * @param a The first integer.
47     * @param b The second integer.
48     * @return The greatest common divisor of a and b.
49     */
50    private int gcd(int a, int b) {
51        // If the second number, b, is 0, return the first number, a.
52        if (b == 0) {
53            return a;
54        }
55        // Keep calling the gcd function recursively, reducing the problem size.
56        return gcd(b, a % b);
57    }
58}
59

1#include <algorithm> // Include algorithm header to use std::gcd
2
3// Definition for singly-linked list node.
4struct ListNode {
5    int val;
6    ListNode *next;
7    ListNode() : val(0), next(nullptr) {} // Default constructor
8    ListNode(int x) : val(x), next(nullptr) {} // Constructor initializing val
9    ListNode(int x, ListNode *next) : val(x), next(next) {} // Constructor initializing both val and next
10};
11
12class Solution {
13public:
14    // Function to insert nodes containing the Greatest Common Divisor (GCD) of the
15    // adjacent nodes' values, between those nodes in the list.
16    ListNode* insertGreatestCommonDivisors(ListNode* head) {
17        if (!head) return nullptr; // Return if the list is empty
18      
19        ListNode* current = head; // Current node is set to the head of the list
20        ListNode* nextNode = head->next; // Next node is the one following current
21      
22        // Iterate over each pair of adjacent nodes until the end of the list
23        while (nextNode) {
24            // Calculate GCD of the values in the current and next nodes
25            int gcdValue = std::gcd(current->val, nextNode->val);
26          
27            // Insert a new node with calculated GCD value between current and next nodes
28            current->next = new ListNode(gcdValue, nextNode);
29          
30            // Move to the next pair of nodes, skipping over the newly inserted node
31            current = nextNode;
32            nextNode = nextNode->next;
33        }
34        return head; // Return the updated list with inserted GCD nodes
35    }
36};
37

1// Type definition for a node in a singly-linked list.
2type ListNode = {
3    val: number;
4    next: ListNode | null;
5};
6
7/**
8 * Inserts the greatest common divisor (GCD) of the values of each pair of adjacent nodes into the list.
9 * @param head the head of the singly-linked list.
10 * @returns the modified list with GCD nodes inserted.
11 */
12function insertGreatestCommonDivisors(head: ListNode | null): ListNode | null {
13    // Pointers for the current and next node in the list
14    let currentNode = head;
15    let nextNode = head?.next;
16
17    // Loop through each pair of adjacent nodes in the list
18    while (nextNode) {
19        // Calculate the GCD of the values of currentNode and nextNode
20        const gcdValue = gcd(currentNode.val, nextNode.val);
21        // Insert a new node with the GCD value between the currentNode and nextNode
22        currentNode.next = { val: gcdValue, next: nextNode };
23        // Move the currentNode pointer to the next node in the original list
24        currentNode = nextNode;
25        // Move the nextNode pointer to the node following the nextNode in the original list
26        nextNode = nextNode.next;
27    }
28
29    return head;
30}
31
32/**
33 * Calculates the greatest common divisor (GCD) of two non-negative integers.
34 * @param a the first integer.
35 * @param b the second integer.
36 * @returns the GCD of a and b.
37 */
38function gcd(a: number, b: number): number {
39    if (b === 0) {
40        return a;
41    }
42    // Recursively call gcd with b and the remainder of a divided by b
43    return gcd(b, a % b);
44}
45

Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the given algorithm is determined by how many times it iterates through the linked list and how many times it computes the greatest common divisor (gcd) for adjacent nodes.

The algorithm traverses each node of the linked list once to insert the computed gcds. If there are n nodes in the list, it makes n-1 computations of gcd because we compute gcd for every pair of adjacent nodes.
The time complexity of the gcd function depends on the values of the nodes. The worst-case scenario for Euclid's algorithm is when the two numbers are consecutive Fibonacci numbers, which leads to a time complexity of O(log(min(a, b))) where a and b are the values of the nodes.

Combining these two factors, the overall time complexity of the algorithm is O(n * log(min(a, b))).

Space Complexity

The space complexity is determined by the additional space needed by the algorithm which is not part of the input. In this case, we are inserting n-1 new nodes to store the gcds, this requires O(n) additional space.

Therefore, the space complexity of the algorithm is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

TrueFalse

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2807. Insert Greatest Common Divisors in Linked List

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings