2197

2197. Replace Non-Coprime Numbers in Array (Hard)

You are given an array of integers nums. Perform the following steps:

1. Find any two adjacent numbers in nums that are non-coprime.
2. If no such numbers are found, stop the process.
3. Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
4. Repeat this process as long as you keep finding two adjacent non-coprime numbers.

Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.

The test cases are generated such that the values in the final array are less than or equal to 108.

Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.

 

Example 1:

Input: nums = [6,4,3,2,7,6,2]
Output: [12,7,6]
Explanation: 
- (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
- (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
- (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
- (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [12,7,6].
Note that there are other ways to obtain the same resultant array.

Example 2:

Input: nums = [2,2,1,1,3,3,3]
Output: [2,1,1,3]
Explanation: 
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3].
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3].
- (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [2,1,1,3].
Note that there are other ways to obtain the same resultant array.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• The test cases are generated such that the values in the final array are less than or equal to 108.

Similar Questions:

• Remove All Adjacent Duplicates in String II (Medium)
• Number of Pairs of Interchangeable Rectangles (Medium)

Solution 1. Simulation + Two Pointers

Intuition: From left to right, replace two adjacent non-coprime numbers with their LCM. When a merge happens, try keep merging leftwards.

Algorithm: i is a read pointer scaning A from left to right. j is a write pointer. After reading a new number A[j] = A[i], we keep trying to merge A[j] with A[j-1] if they are non-coprime. The new A[j-1] after merge is LCM(A[j], A[j-1]).

Time Complexity:

Since gcd(a, b)'s time complexity is log(min(a, b)), the time complexity is O(NlogM) overall where M is the maximum number in A.

// OJ: https://leetcode.com/problems/replace-non-coprime-numbers-in-array/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1) extra space
class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& A) {
        int j = 0, N = A.size();
        for (int i = 0; i < N; ++i, ++j) {
            A[j] = A[i];
            for (; j - 1 >= 0 && gcd(A[j], A[j - 1]) > 1; --j) { // When we can merge leftwards from `A[j]`, keep merging
                A[j - 1] = (long)A[j] * A[j - 1] / gcd(A[j], A[j - 1]); // replace `A[j-1]` with LCM of `A[j-1]` and `A[j]`.
            }
        }
        A.resize(j);
        return A;
    }
};

Discuss

https://leetcode.com/problems/replace-non-coprime-numbers-in-array/discuss/1823592/