Formatted question description: https://leetcode.ca/all/2197.html

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

You are given an array of integers `nums`

. Perform the following steps:

- Find
**any**two**adjacent**numbers in`nums`

that are**non-coprime**. - If no such numbers are found,
**stop**the process. - Otherwise, delete the two numbers and
**replace**them with their**LCM (Least Common Multiple)**. **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 `10`

.^{8}

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 = [,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,12]. 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.6

**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) 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 = [3,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.2

**Constraints:**

`1 <= nums.length <= 10`

^{5}`1 <= nums[i] <= 10`

^{5}- The test cases are generated such that the values in the final array are
**less than or equal**to`10`

.^{8}

**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/
// 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/