# Replace Non-Coprime Numbers in Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/replace-non-coprime-numbers-in-array)
Canonical: https://scaleengineer.com/dsa/problems/replace-non-coprime-numbers-in-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array, Stack
---
## Problem
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`.

# Approaches
## Brute-Force Simulation with Rescanning
This approach directly simulates the process described in the problem. It uses a dynamic list to store the numbers. In a loop, it scans the list for any adjacent non-coprime pair. If found, it replaces them with their LCM and restarts the scan from the beginning of the now-modified list. This continues until a full scan finds no non-coprime pairs.
**Time:** O(N^3). In the worst case, we might perform O(N) merges. Each merge could require a scan of up to O(N) elements. The list modification itself takes O(N). So, one pass that results in a merge takes O(N^2). With O(N) merges, this leads to O(N^3). The O(log M) factor for GCD is dominated. · **Space:** O(N) to store the list of numbers.
**Pros:** Simple to understand and directly follows the problem description.
**Cons:** Highly inefficient due to repeated scanning from the beginning after every merge.; Modifying a list (like `ArrayList`) by removing and inserting elements in the middle is a slow operation (`O(N)`).
### Explanation
The algorithm maintains the array of numbers in a data structure that allows for efficient removal and insertion, such as Java's `ArrayList`. It enters a primary `while` loop that continues as long as modifications are being made to the list. A boolean flag, say `merged`, can track this. Inside the loop, `merged` is reset to `false`, and a `for` loop iterates through the current list to find an adjacent non-coprime pair `(list.get(i), list.get(i+1))`. To check for non-coprimality, we compute `GCD(a, b)`. If `GCD > 1`, the numbers are non-coprime. Upon finding such a pair, we calculate their `LCM`. The two numbers are removed from the list, and their LCM is inserted at the position of the first number. The `merged` flag is set to `true`, and we `break` the inner `for` loop to restart the scan from the beginning of the updated list. This is crucial because the new LCM might be non-coprime with its new left neighbor. If the inner `for` loop completes without finding any non-coprime pairs (`merged` remains `false`), the main `while` loop terminates. The final list is then returned.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.Arrays;

class Solution {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Long> list = new ArrayList<>();
        for (int num : nums) {
            list.add((long) num);
        }

        while (true) {
            boolean mergedInPass = false;
            for (int i = 0; i < list.size() - 1; i++) {
                long a = list.get(i);
                long b = list.get(i + 1);
                long commonDivisor = gcd(a, b);

                if (commonDivisor > 1) {
                    list.remove(i + 1);
                    list.set(i, lcm(a, b, commonDivisor));
                    mergedInPass = true;
                    break; // Restart scan
                }
            }
            if (!mergedInPass) {
                break;
            }
        }

        return list.stream().map(Long::intValue).collect(Collectors.toList());
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private long lcm(long a, long b, long gcd) {
        return (a / gcd) * b;
    }
}
```
### Algorithm
- Convert the input array `nums` to a `List<Integer>`.
- Start an outer loop `while(true)`.
- Initialize a boolean `mergedInPass = false`.
- Start an inner loop to iterate from `i = 0` to `list.size() - 2`.
- Get adjacent numbers `a = list.get(i)` and `b = list.get(i+1)`.
- Calculate `g = GCD(a, b)`.
- If `g > 1`:
    - Calculate `l = LCM(a, b)`.
    - Remove elements at `i` and `i+1`.
    - Insert `l` at index `i`.
    - Set `mergedInPass = true`.
    - `break` the inner loop.
- If `mergedInPass` is `false` after the inner loop, `break` the outer loop.
- Return the final list.

## In-place Simulation with Backtracking
This is an optimization over the brute-force approach. Instead of restarting the scan from the beginning after a merge, we only backtrack one step. When two numbers at indices `i-1` and `i` are merged, the new LCM is placed at `i-1`. This new number might be non-coprime with the element at `i-2`. So, we just need to move our check pointer `i` back one position to handle this potential new merge.
**Time:** O(N^2). The main loop pointer `i` makes N forward moves in total and can make O(N) backward moves. So the loop runs O(N) times. Inside the loop, `list.remove(i)` can take O(N) time in the worst case. This results in a total time complexity of O(N^2). The O(log M) factor for GCD is dominated. · **Space:** O(N) to store the list.
**Pros:** More efficient than full rescanning as it avoids redundant checks on parts of the array that haven't changed.
**Cons:** Still suffers from the O(N) cost of element removal in an `ArrayList`, leading to a quadratic time complexity.
### Explanation
This method also uses a dynamic list like `ArrayList`. It iterates through the list with a single pointer `i`, starting from `1`. At each position `i`, it checks the pair `(list.get(i-1), list.get(i))`. If they are non-coprime (`GCD > 1`), it calculates their LCM, replaces the element at `i-1` with the LCM, and removes the element at `i`. Crucially, it then decrements the pointer `i`. If `i` was `1`, it becomes `0`, and the loop condition `i < list.size()` will re-evaluate. The next iteration will start with `i=1` again, effectively re-checking from the start of the modified section. If `i > 1`, it becomes `i-1`, so the next check will be between the new LCM and its new left neighbor. If the numbers are coprime, we simply increment `i` to move to the next pair. The process continues until `i` traverses the entire list.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.Arrays;

class Solution {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Long> list = new ArrayList<>();
        for (int num : nums) {
            list.add((long) num);
        }

        int i = 1;
        while (i < list.size()) {
            long a = list.get(i - 1);
            long b = list.get(i);
            long commonDivisor = gcd(a, b);

            if (commonDivisor > 1) {
                list.set(i - 1, lcm(a, b, commonDivisor));
                list.remove(i);
                if (i > 1) {
                    i--; // Backtrack to check with the previous element
                }
            } else {
                i++;
            }
        }

        return list.stream().map(Long::intValue).collect(Collectors.toList());
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private long lcm(long a, long b, long gcd) {
        return (a / gcd) * b;
    }
}
```
### Algorithm
- Convert the input array `nums` to a `List<Long>` to handle intermediate LCM values.
- Initialize an index `i = 1`.
- `while (i < list.size())`:
    - Get `a = list.get(i-1)` and `b = list.get(i)`.
    - Calculate `g = GCD(a, b)`.
    - If `g > 1`:
        - Calculate `l = LCM(a, b)`.
        - Set `list.set(i-1, l)`.
        - Remove element at `i` using `list.remove(i)`.
        - If `i > 1`, decrement `i` (`i--`).
    - Else (`g == 1`):
        - Increment `i` (`i++`).
- Return the final list.

## Efficient Simulation using a Stack
This is the most efficient approach. It rephrases the problem in a way that is perfectly suited for a stack data structure. We process the input numbers one by one. Each new number is conceptually 'pushed' onto a result stack. Then, we repeatedly check if the top two elements of the stack are non-coprime. If they are, we 'pop' them, compute their LCM, and 'push' the result back. This continues until the top two are coprime or the stack has fewer than two elements.
**Time:** O(N * log M). Each of the N numbers is processed once. For each number, it might trigger a chain of merges with elements already in the stack. However, each merge operation reduces the size of the stack by one. In total, there are N pushes and at most N-1 merges. Each operation involves a GCD calculation, which takes O(log M), where M is the maximum possible value. Thus, the total time is dominated by the GCD calculations. · **Space:** O(N) in the worst case (if all numbers are pairwise coprime), the result list will store all N numbers.
**Pros:** Optimal time complexity.; Each number is pushed onto the stack once. The total number of merge operations is bounded by N.; Operations at the end of an `ArrayList` or `LinkedList` (add, remove last) are amortized O(1).
**Cons:** The logic is slightly less direct than a straightforward simulation, but it's a standard and powerful pattern.
### Explanation
The core idea is that when we add a new number, it only needs to be checked against its most recent predecessor. If they merge, the resulting new number needs to be checked against *its* most recent predecessor, and so on. This 'last-in, first-out' pattern of interaction is the hallmark of a stack. We can use an `ArrayList` or a `LinkedList` to act as a stack, as we only need efficient access to the end of the list. We iterate through each number `num` from the input array `nums`. For each `num`, we add it to our result list. Then, we enter a `while` loop that runs as long as the result list has at least two elements and the last two elements are non-coprime. Inside the `while` loop, we remove the last two elements (`a` and `b`), calculate their LCM, and add the LCM back to the end of the list. This process ensures that any non-coprime chain reaction is fully resolved before moving to the next number from the input array. After iterating through all numbers in `nums`, the result list holds the final sequence.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.LinkedList;

class Solution {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        LinkedList<Long> res = new LinkedList<>();
        for (int num : nums) {
            long currentNum = num;
            while (!res.isEmpty()) {
                long prevNum = res.getLast();
                long commonDivisor = gcd(prevNum, currentNum);
                if (commonDivisor > 1) {
                    currentNum = lcm(prevNum, currentNum, commonDivisor);
                    res.removeLast();
                } else {
                    break;
                }
            }
            res.add(currentNum);
        }

        List<Integer> finalList = new ArrayList<>();
        for (long val : res) {
            finalList.add((int) val);
        }
        return finalList;
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private long lcm(long a, long b, long gcd) {
        return (a / gcd) * b;
    }
}
```
### Algorithm
- Initialize an empty list, `res`, to be used as a stack.
- For each `num` in the input array `nums`:
    - Add `num` to the end of `res`.
    - `while (res.size() > 1)`:
        - Get the last two elements: `y = res.get(res.size()-1)` and `x = res.get(res.size()-2)`.
        - Calculate `g = GCD(x, y)`.
        - If `g > 1`:
            - Remove the last two elements from `res`.
            - Calculate `l = LCM(x, y)`.
            - Add `l` to the end of `res`.
        - Else (`g == 1`):
            - `break` the `while` loop.
- Return `res`.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> replaceNonCoprimes(int[] nums) {
    List<Integer> stk = new ArrayList<>();
    for (int x : nums) {
      stk.add(x);
      while (stk.size() > 1) {
        x = stk.get(stk.size() - 1);
        int y = stk.get(stk.size() - 2);
        int g = gcd(x, y);
        if (g == 1) {
          break;
        }
        stk.remove(stk.size() - 1);
        stk.set(stk.size() - 1, (int)((long)x * y / g));
      }
    }
    return stk;
  }
private
  int gcd(int a, int b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> replaceNonCoprimes(vector<int> &nums) {
    vector<int> stk;
    for (int x : nums) {
      stk.push_back(x);
      while (stk.size() > 1) {
        x = stk.back();
        int y = stk[stk.size() - 2];
        int g = __gcd(x, y);
        if (g == 1) {
          break;
        }
        stk.pop_back();
        stk.back() = 1LL * x * y / g;
      }
    }
    return stk;
  }
};

```

### Python

```python
class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]: stk = [] for x in nums: stk . append(x) while len(stk) > 1: x, y = stk[- 2:] g = gcd(x, y) if g == 1: break stk . pop() stk[- 1] = x * y // g return stk

```