Replace Non-Coprime Numbers in Array

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 thefinal 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.

Examples

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 <= 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 108.

Solution

Method 1 - Stack Simulation with GCD/LCM

Intuition

We want to repeatedly merge adjacent non-coprime numbers into their LCM until no such pairs remain. Using a stack, we can efficiently simulate this process: for each number, merge it with the top of the stack as long as the GCD is greater than 1.

Approach

1. Initialize an empty stack.
2. For each number in nums:
   • While the stack is not empty and the top and current number are non-coprime (GCD > 1), pop the top and replace current with LCM(top, current).
   • Push the current number onto the stack.
3. The stack contains the final array.

Code

C++

#include <vector>
#include <numeric>
using namespace std;

vector<int> replaceNonCoprimes(vector<int>& nums) {
    vector<int> stk;
    for (int x : nums) {
        while (!stk.empty()) {
            int g = gcd(stk.back(), x);
            if (g == 1) break;
            x = lcm(stk.back(), x);
            stk.pop_back();
        }
        stk.push_back(x);
    }
    return stk;
}

Go

import "math"
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func lcm(a, b int) int {
    return a / gcd(a, b) * b
}
func replaceNonCoprimes(nums []int) []int {
    stk := []int{}
    for _, x := range nums {
        for len(stk) > 0 && gcd(stk[len(stk)-1], x) > 1 {
            x = lcm(stk[len(stk)-1], x)
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, x)
    }
    return stk
}

Java

import java.util.*;
public class Solution {
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
    private int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Integer> stk = new ArrayList<>();
        for (int x : nums) {
            while (!stk.isEmpty() && gcd(stk.get(stk.size()-1), x) > 1) {
                x = lcm(stk.remove(stk.size()-1), x);
            }
            stk.add(x);
        }
        return stk;
    }
}

Kotlin

fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
fun lcm(a: Int, b: Int): Int = a / gcd(a, b) * b
fun replaceNonCoprimes(nums: IntArray): List<Int> {
    val stk = mutableListOf<Int>()
    for (x0 in nums) {
        var x = x0
        while (stk.isNotEmpty() && gcd(stk.last(), x) > 1) {
            x = lcm(stk.removeAt(stk.size-1), x)
        }
        stk.add(x)
    }
    return stk
}

Python

from math import gcd
from typing import List
def lcm(a, b):
    return a * b // gcd(a, b)
def replaceNonCoprimes(nums: List[int]) -> List[int]:
    stk = []
    for x in nums:
        while stk and gcd(stk[-1], x) > 1:
            x = lcm(stk.pop(), x)
        stk.append(x)
    return stk

Rust

fn gcd(mut a: i64, mut b: i64) -> i64 {
    while b != 0 {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}
fn lcm(a: i64, b: i64) -> i64 {
    a / gcd(a, b) * b
}
fn replace_non_coprimes(nums: Vec<i64>) -> Vec<i64> {
    let mut stk = Vec::new();
    for mut x in nums {
        while let Some(&last) = stk.last() {
            if gcd(last, x) == 1 { break; }
            x = lcm(stk.pop().unwrap(), x);
        }
        stk.push(x);
    }
    stk
}

TypeScript

function gcd(a: number, b: number): number {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
function lcm(a: number, b: number): number {
    return a / gcd(a, b) * b;
}
function replaceNonCoprimes(nums: number[]): number[] {
    const stk: number[] = [];
    for (let x of nums) {
        while (stk.length && gcd(stk[stk.length-1], x) > 1) {
            x = lcm(stk.pop()!, x);
        }
        stk.push(x);
    }
    return stk;
}

Complexity

• ⏰ Time complexity: O(N log M), where N is the length of nums and M is the max value in nums (for GCD/LCM).
• 🧺 Space complexity: O(N), for the stack.