Replace Non-Coprime Numbers in Array

hard stack math number theory

Problem

You are given an array of integers nums. Repeatedly scan for any two adjacent values that are non-coprime (their greatest common divisor is greater than 1) and replace that pair with a single number equal to their least common multiple (LCM). Keep doing this until no adjacent pair shares a common factor. The final array is unique no matter which order the merges happen in. Return that array.

Inputnums = [6, 4, 3, 2, 7, 6, 2]

Output[12, 7, 6]

6, 4, 3, 2 all chain together via common factors and collapse into lcm = 12. 7 is coprime with both neighbours. The trailing 6 and 2 merge into lcm = 6.

nums (comma-separated positive integers)

from math import gcd

def replace_non_coprimes(nums):
    stack = []
    for x in nums:
        while stack:
            g = gcd(stack[-1], x)
            if g == 1:
                break
            x = stack.pop() // g * x
        stack.append(x)
    return stack

function gcd(a, b) {
  while (b) { [a, b] = [b, a % b]; }
  return a;
}
function replaceNonCoprimes(nums) {
  const stack = [];
  for (let x of nums) {
    while (stack.length) {
      const g = gcd(stack[stack.length - 1], x);
      if (g === 1) break;
      x = stack.pop() / g * x;
    }
    stack.push(x);
  }
  return stack;
}

class Solution {
    private long gcd(long a, long b) {
        while (b != 0) { long t = a % b; a = b; b = t; }
        return a;
    }
    public List<Integer> replaceNonCoprimes(int[] nums) {
        Deque<Long> stack = new ArrayDeque<>();
        for (int v : nums) {
            long x = v;
            while (!stack.isEmpty()) {
                long g = gcd(stack.peek(), x);
                if (g == 1) break;
                x = stack.pop() / g * x;
            }
            stack.push(x);
        }
        List<Integer> res = new ArrayList<>();
        for (long v : stack) res.add(0, (int) v);
        return res;
    }
}

long long gcdll(long long a, long long b) {
    while (b) { long long t = a % b; a = b; b = t; }
    return a;
}
vector<int> replaceNonCoprimes(vector<int>& nums) {
    vector<long long> stack;
    for (int v : nums) {
        long long x = v;
        while (!stack.empty()) {
            long long g = gcdll(stack.back(), x);
            if (g == 1) break;
            x = stack.back() / g * x;
            stack.pop_back();
        }
        stack.push_back(x);
    }
    return vector<int>(stack.begin(), stack.end());
}

Explanation

Two numbers are non-coprime when they share a factor bigger than 1, i.e. gcd > 1. When a non-coprime pair appears side by side we collapse them into their least common multiple, using the identity lcm(a, b) = a / gcd(a, b) * b. Dividing before multiplying keeps the number from overflowing.

The key insight is that this collapsing behaves exactly like matching brackets: after merging a pair into one value, that fresh value can suddenly become non-coprime with the element on its left, triggering another merge. A stack captures this perfectly — the top of the stack is always the candidate left-neighbour for whatever number we are placing.

For each incoming number x, we look at the stack top. While the top and x are non-coprime, we pop the top, fold it into x via the LCM, and keep checking against the new top. Once the top is coprime with x (or the stack is empty), we push x and move on. Because merges only chain leftward and every original element is pushed once and popped at most once, the whole process is linear in spirit.

Example: nums = [6, 4, 3, 2, 7, 6, 2]. The 6 enters. The 4 shares factor 2, so they merge into lcm(6, 4) = 12. The 3 shares factor 3 with 12, giving lcm(12, 3) = 12. The 2 shares factor 2, still 12. Then 7 is coprime with 12, so it sits on top. The next 6 is coprime with 7, so it is pushed. Finally 2 shares factor 2 with 6, merging into lcm(6, 2) = 6; that 6 is coprime with 7, so it stays. The stack reads [12, 7, 6].

It does not matter which adjacent pair you choose to merge first — the result is always the same array, so the stack-based left-to-right sweep is a valid order.

Time: O(n log m) Space: O(n)