DDSA Solutions

2807. Insert Greatest Common Divisors in Linked List

MediumView on LeetCode
ArrayMathLinked ListNumber Theory
Time: O(n log max)
Space: O(1)

Problem Overview

Insert greatest common divisors between every pair of adjacent elements.

Intuition

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

Algorithm

  1. 1For each adjacent pair (nums[i], nums[i+1]): compute GCD, insert between them.
  2. 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
C#
// 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?

Related Problems