Dare2Solve
Given a singly linked list, you are required to insert a node with the greatest common divisor (GCD) of two consecutive node values between every two adjacent nodes. This will modify the list in such a way that for each pair of consecutive nodes, a new node is inserted with the value of the GCD of their values.
To solve this problem, we can calculate the GCD of two consecutive nodes in the linked list and insert a new node with this GCD value in between them. We iterate through the list and apply this process until we reach the end of the list.
The GCD of two numbers is the largest number that divides both numbers without leaving a remainder. We can compute the GCD either through iterative or recursive approaches.
Helper Function for GCD: We create a helper function to compute the GCD of two numbers. This can be done by iterating through all numbers from 2 to the smaller of the two numbers and checking which is the largest divisor common to both.
Iterating Through the List: We traverse the linked list starting from the head. For each pair of consecutive nodes, we compute their GCD and insert a new node with this value between the two nodes.
Insertion: After computing the GCD for a pair of nodes, we create a new node with the GCD value and adjust the next
pointers to insert the node between the current node and the next node.
Repeat: We continue this process until the end of the list, modifying the list in place by adding new nodes.
a
and b
are the two numbers.n
nodes, we perform this operation n - 1
times (once between each consecutive pair of nodes). Therefore, the time complexity is O(n * min(a, b)), where n
is the number of nodes in the list.n
is the number of original nodes, as each insertion creates an additional node.class Solution {
public:
int findGCD(int num1, int num2) {
int smaller = std::min(num1, num2);
int maxGCD = 1;
for (int i = 2; i <= smaller; i++) {
if (num1 % i == 0 && num2 % i == 0) {
maxGCD = i;
}
}
return maxGCD;
}
ListNode* insertGreatestCommonDivisors(ListNode* head) {
ListNode* curr = head;
while (curr->next != nullptr) {
ListNode* next = curr->next;
int gcd = findGCD(curr->val, next->val);
curr->next = new ListNode(gcd, next);
curr = curr->next->next;
}
return head;
}
};
class Solution:
def findGCD(self, num1, num2):
smaller = min(num1, num2)
max_gcd = 1
for i in range(2, smaller + 1):
if num1 % i == 0 and num2 % i == 0:
max_gcd = i
return max_gcd
def insertGreatestCommonDivisors(self, head):
curr = head
while curr.next:
next_node = curr.next
gcd = self.findGCD(curr.val, next_node.val)
curr.next = ListNode(gcd, next_node)
curr = curr.next.next
return head
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
private int findGCD(int num1, int num2) {
int smaller = Math.min(num1, num2);
int maxGCD = 1;
for (int i = 2; i <= smaller; i++) {
if (num1 % i == 0 && num2 % i == 0) {
maxGCD = i;
}
}
return maxGCD;
}
public ListNode insertGreatestCommonDivisors(ListNode head) {
ListNode curr = head;
while (curr.next != null) {
ListNode next = curr.next;
int gcd = findGCD(curr.val, next.val);
curr.next = new ListNode(gcd, next);
curr = curr.next.next;
}
return head;
}
}
var insertGreatestCommonDivisors = function (head) {
let findGCD = function (num1, num2) {
let smaller = Math.min(num1, num2)
let max = 1
for (let i = 2; i <= smaller; i++) {
if (num1 % i === 0 && num2 % i === 0) {
max = i
}
}
return max
}
let curr = head
while (curr.next) {
let next = curr.next
let gcd = findGCD(curr.val, next.val)
curr.next = new ListNode(gcd, next)
curr = curr.next.next
}
return head
}