Create 2197.Replace-Non-Coprime-Numbers-in-Array.cpp

wisdompeak · web-flow · commit a203120c4eb6 · 2022-03-13T00:57:49.000-08:00
diff --git a/Stack/2197.Replace-Non-Coprime-Numbers-in-Array/2197.Replace-Non-Coprime-Numbers-in-Array.cpp b/Stack/2197.Replace-Non-Coprime-Numbers-in-Array/2197.Replace-Non-Coprime-Numbers-in-Array.cpp
@@ -0,0 +1,23 @@
+class Solution {
+public:
+    vector<int> replaceNonCoprimes(vector<int>& nums) 
+    {
+        vector<int>rets;
+        for (int i=0; i<nums.size(); i++)
+        {
+            int x = nums[i];
+            while (!rets.empty() && gcd(rets.back(), x)>1)
+            {
+                x = lcm(rets.back(), x);
+                rets.pop_back();                
+            }
+            rets.push_back(x);
+        }
+        return rets;        
+    }
+
+    long long lcm(long long a, long long b)
+    {
+        return (long long)a*(long long)b/gcd(a,b);
+    }
+};
