LeetCode Daily Problem P2197 Replace Non-Coprime Numbers in Array

---

Timeline

timeline

2025-09-16

init

lcm least common multiple, gcd greatest common divisor, stack

---

Problem:

P2197 Replace Non-Coprime Numbers in Array

https://leetcode.cn/problems/replace-non-coprime-numbers-in-array/description/?envType=daily-question&envId=2025-09-16

<numeric>There are std::lcm and std::gcd for calculating least common multiple and greatest common divisor respectively

#include <numeric>
#include <vector>

using std::vector;

class Solution {
    public:
        vector<int> replaceNonCoprimes(vector<int> &nums)
        {
                int n = nums.size();
                // Use nums[0..top] as a "stack"
                int top = 0;
                for (int i = 1; i < n; i++) {
                        // std::gcd greatest common divisor
                        // If the top of stack nums[top] and current nums[i] are not coprime, merge them.
                        // A number may be continuously non-coprime with multiple preceding numbers.
                        // So we must keep merging backwards until it is coprime with the top of stack.
                        while (top >= 0 and std::gcd(nums[top], nums[i]) > 1) {
                                // std::lcm least common multiple
                                nums[i] = std::lcm(nums[top], nums[i]);
                                // Pop the top of the stack, continue comparing with the new top
                                top--;
                        }
                        // Push the merged result back onto the top of the stack
                        nums[++top] = nums[i];
                }
                nums.resize(top + 1);
                return nums;
        }
};