2807. Insert Greatest Common Divisors in Linked List

MediumView on LeetCode

Array Math Linked List Number Theory

Time: O(n log max)

Space: O(1)

Intuition

Insert greatest common divisors between every pair of adjacent elements. GCD of adjacent pair inserted between them.

Algorithm

1For each adjacent pair (nums[i], nums[i+1]): compute GCD, insert between them.
2Build new array with original elements and inserted GCDs.

Common Pitfalls

•New array has 2n-1 elements. GCD computed for original adjacent pairs only.

2807.cs

// Approach: Traverse list; insert new node with GCD(a, b) between each consecutive pair.
// Time: O(n log max) Space: O(1)

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode InsertGreatestCommonDivisors(ListNode head)
    {
        for (ListNode curr = head; curr.next != null;)
        {
            ListNode inserted = new ListNode(Gcd(curr.val, curr.next.val), curr.next);
            curr.next = inserted;
            curr = inserted.next;
        }
        return head;
    }

    private int Gcd(int a, int b)
    {
        return b == 0 ? a : Gcd(b, a % b);
    }
}

Was this solution helpful?