aboutsummaryrefslogtreecommitdiff
path: root/replace_non_coprime_nums.py
diff options
context:
space:
mode:
Diffstat (limited to 'replace_non_coprime_nums.py')
-rw-r--r--replace_non_coprime_nums.py36
1 files changed, 36 insertions, 0 deletions
diff --git a/replace_non_coprime_nums.py b/replace_non_coprime_nums.py
new file mode 100644
index 0000000..8707c8d
--- /dev/null
+++ b/replace_non_coprime_nums.py
@@ -0,0 +1,36 @@
+# 2197. Replace Non-Coprime Numbers in Array
+from math import gcd
+
+"""
+you are given an array of integers 'nums'. perform the following steps: find
+any two adjacent numbers in 'nums' that are non-coprime, if no such numbers
+are found, stop the process. otherwise, delete the two numbers and replace
+them with their lcm. repeat this process as long as you keep finding two
+adjacent non-coprime integers. return the final modified array. it can be
+shown that replacing adjacent non-coprime numbers in any arbitrary order will
+lead to the same result. two values 'x' and '' aree non-coprime if 'gcd(x, y)
+> 1' where 'gcd(x, y)' is the greatest common denomiator
+"""
+
+
+class Solution(object):
+ def replaceNonCoprimes(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: List[int]
+ """
+ ans = []
+ for i in nums:
+ while ans:
+ g = gcd(ans[-1], i)
+ if g == 1:
+ break
+ i = (ans.pop() * i) // g
+ ans.append(i)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.replaceNonCoprimes(nums=[6, 4, 3, 2, 7, 6, 2]))
+ print(obj.replaceNonCoprimes(nums=[2, 2, 1, 1, 3, 3, 3]))