2197: Replace-Non-Coprime-Numbers-in-Array
Hard

table of contents

The premise is simple. First, you unnecessarily define the Euclidean Algorithm because you forgot the gcd function exists:

private {
    int euclideanAlgorithm(int n1, int n2) {
        int remainder = -1;
        if (n2 > n1) swap(n1, n2);
        while (remainder != 0) {
            remainder = n1 - (n1/n2) * n2;
            n1 = n2;
            n2 = remainder;
        }
        return n1;
    }
}

Then, you initialize a stack…

vector<int> ans;
ans.push_back(nums[0]);

…and iterate through nums, checking if your current value is coprime to the top of the stack.

for (int i = 1; i < nums.size(); ++i) {
    int GCD = euclideanAlgorithm(ans.back(), nums[i]);
    if (GCD != 1) {
        int curr = static_cast<long long>(nums[i]) * ans.back() / GCD;
        ans.pop_back();
        while (!ans.empty() && GCD != 1) {
            GCD = euclideanAlgorithm(ans.back(), curr);
            if (GCD != 1) {
                curr = static_cast<long long>(curr) * ans.back() / GCD;
                ans.pop_back();
            }
        }
        ans.push_back(curr);
    } else {
        ans.push_back(nums[i]);
    }
}

Finally, you can be happy that you are free because this question was definitely not a hard difficulty question at all ahhhhhhh

return ans;

code

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> ans;
        ans.push_back(nums[0]);
        for (int i = 1; i < nums.size(); ++i) {
            int GCD = euclideanAlgorithm(ans.back(), nums[i]);
            if (GCD != 1) {
                int curr = static_cast<long long>(nums[i]) * ans.back() / GCD;
                ans.pop_back();
                while (!ans.empty() && GCD != 1) {
                    GCD = euclideanAlgorithm(ans.back(), curr);
                    if (GCD != 1) {
                        curr = static_cast<long long>(curr) * ans.back() / GCD;
                        ans.pop_back();
                    }
                }
                ans.push_back(curr);
            } else {
                ans.push_back(nums[i]);
            }
        }
        return ans;
    }
private:
    int euclideanAlgorithm(int n1, int n2) {
        int remainder = -1;
        if (n2 > n1) swap(n1, n2);
        while (remainder != 0) {
            remainder = n1 - (n1/n2) * n2;
            n1 = n2;
            n2 = remainder;
        }
        return n1;
    }
};

complexity

learnings

time taken