2197. Replace Non Coprime Numbers in Array

Problem Description

Given an array A of positive integers, the task is to replace the adjacent non-coprime numbers with their Least Common Multiple (LCM), until it's not possible to do any more merges. A pair of numbers (a, b) are called non-coprime if their Greatest Common Divisor (GCD) is greater than 1. The final array should be as short as possible.

Example:

Input: nums = [4, 6, 7, 30]

Output: [4, 6, 7, 30]

Explanation:

• The first pair of numbers (4, 6) have GCD of 2, so they are non-coprime. Replace them with their LCM, which is 12.
• The resulting array is [12, 7, 30]. There are no more adjacent non-coprime numbers, so the array is final.

Approach

1. Initialize two pointers, i as a read pointer, and j as a write pointer, both starting from the first element of the input array nums.
2. Iterate over the array with the read pointer i. For each number num at position i, try to merge it with the previous number ans[j-1], as long as they are non-coprime. The merging is done by calculating the LCM of ans[j-1] and num, replacing ans[j-1] with the LCM, and popping the last element of ans.
3. Push the merged number or the original number to the back of ans.
4. Repeat steps 2-3 for all elements in the input array.
5. Return the resulting array ans as the output.

Time Complexity

The time complexity of the algorithm is O(NlogM), where N is the number of elements in the input array, and M is the maximum number in the input array. This is because the time complexity of calculating GCD(a, b) is log(min(a, b)).

Example Walkthrough

Let's walk through the provided example:

Input: nums = [4, 6, 7, 30]

1. Initialize read pointer i and write pointer j
2. Iterate over the input array with the read pointer i
   • i = 0, num = 4, push 4 to ans: ans = [4]
   • i = 1, num = 6, GCD(4, 6) > 1, so merge 4 and 6 by calculating LCM(4, 6) = 12, ans = [12]
   • i = 2, num = 7, GCD(12, 7) = 1, push 7 to ans: ans = [12, 7]
   • i = 3, num = 30, GCD(7, 30) = 1, push 30 to ans: ans = [12, 7, 30]
3. The final array is [12, 7, 30], which is our output.

Python Solution

1
2python
3from math import gcd
4
5class Solution:
6    def replaceNonCoprimes(self, nums):
7        ans = []
8
9        for num in nums:
10            while ans and gcd(ans[-1], num) > 1:
11                num = (ans[-1] * num) // gcd(ans[-1], num)
12                ans.pop()
13            ans.append(num)
14
15        return ans

Java Solution

1
2java
3import java.util.ArrayList;
4import java.util.List;
5
6class Solution {
7    public List<Integer> replaceNonCoprimes(int[] nums) {
8        List<Integer> ans = new ArrayList<>();
9
10        for (int num : nums) {
11            while (!ans.isEmpty() && gcd(ans.get(ans.size() - 1), num) > 1) {
12                num = lcm(ans.get(ans.size() - 1), num);
13                ans.remove(ans.size() - 1);
14            }
15            ans.add(num);
16        }
17
18        return ans;
19    }
20
21    private int gcd(int a, int b) {
22        if (b == 0) {
23            return a;
24        } else {
25            return gcd(b, a % b);
26        }
27    }
28
29    private int lcm(int a, int b) {
30        return a * b / gcd(a, b);
31    }
32}

JavaScript Solution

1
2javascript
3class Solution {
4    replaceNonCoprimes(nums) {
5        const ans = [];
6
7        for (const num of nums) {
8            while (ans.length > 0 && this.gcd(ans[ans.length - 1], num) > 1) {
9                const temp = ans.pop();
10                ans.push(this.lcm(temp, num));
11            }
12            ans.push(num);
13        }
14
15        return ans;
16    }
17
18    gcd(a, b) {
19        if (b === 0) {
20            return a;
21        } else {
22            return this.gcd(b, a % b);
23        }
24    }
25
26    lcm(a, b) {
27        return a * b / this.gcd(a, b);
28    }
29}

C++ Solution

1
2cpp
3#include <algorithm>
4#include <vector>
5
6class Solution {
7public:
8    std::vector<int> replaceNonCoprimes(std::vector<int>& nums) {
9        std::vector<int> ans;
10
11        for (int num : nums) {
12            while (!ans.empty() && std::gcd(ans.back(), num) > 1) {
13                num = std::lcm(ans.back(), num);
14                ans.pop_back();
15            }
16            ans.push_back(num);
17        }
18
19        return ans;
20    }
21};

C# Solution

1
2csharp
3using System;
4using System.Collections.Generic;
5
6public class Solution {
7    public IList<int> ReplaceNonCoprimes(int[] nums) {
8        List<int> ans = new List<int>();
9
10        foreach (int num in nums) {
11            while (ans.Count > 0 && Gcd(ans[ans.Count - 1], num) > 1) {
12                num = Lcm(ans[ans.Count - 1], num);
13                ans.RemoveAt(ans.Count - 1);
14            }
15            ans.Add(num);
16        }
17
18        return ans;
19    }
20
21    private int Gcd(int a, int b) {
22        if (b == 0) {
23            return a;
24        } else {
25            return Gcd(b, a % b);
26        }
27    }
28
29    private int Lcm(int a, int b) {
30        return a * b / Gcd(a, b);
31    }
32}

Now that we have provided the solutions for Python, Java, JavaScript, C++, and C#, the article is deemed complete. The approach is explained in detail, which allows the reader to understand the problem and its solution. The solutions in different programming languages cover the most widely used languages, ensuring that almost every reader will find a solution in a language they are more comfortable with.

Solution Implementation