Replace Non-Coprime Numbers in Array | Leetcode 2197

class Solution {
    int findGCD(int a,int b){
        if(a==0)
            return b;
        return findGCD(b%a, a);
    }
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> st;
        int n = nums.size();

        for(int i=0;i<n;++i){
            int gcd;
            int curr = nums[i];
            while(st.size()>0){
                gcd = findGCD(st.back(),curr);
                if(gcd==1)
                    break;
                long long lcm = (1LL * st.back() * curr) / gcd;
                st.pop_back();
                curr = lcm;
            }
            st.push_back(curr);
        }
        return st;
    }
};
/*
// JAVA
class Solution {
    private long gcd(long a, long b) {
        while (a != 0) {
            long t = b % a;
            b = a;
            a = t;
        }
        return b;
    }

    public int[] replaceNonCoprimes(int[] nums) {
        Deque<Long> st = new ArrayDeque<>();
        for (int x : nums) {
            long curr = x;
            while (!st.isEmpty()) {
                long g = gcd(st.peekLast(), curr);
                if (g == 1) break;
                // <-- corrected line: use curr and safe order (a/g) * b
                long lcm = (st.peekLast() / g) * curr;
                st.removeLast();
                curr = lcm;
            }
            st.addLast(curr);
        }

        int m = st.size();
        int[] res = new int[m];
        for (int i = m - 1; i >= 0; --i) {
            res[i] = (int) (long) st.removeLast(); // cast to int for return
        }
        return res;
    }
}

#Python
from typing import List
from math import gcd

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        st: List[int] = []
        for x in nums:
            curr = x
            while st:
                g = gcd(st[-1], curr)
                if g == 1:
                    break
                # <-- corrected line: use curr and safe order (a//g) * b
                lcm = (st[-1] // g) * curr
                st.pop()
                curr = lcm
            st.append(curr)
        return st
*/