aboutsummaryrefslogtreecommitdiff
path: root/replace_non_coprime_nums.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-15 20:30:09 -0600
committerJack Sangdahl <[email protected]>2025-09-15 20:30:09 -0600
commitb7cd5b2d6cb9a619e68bc518a369b5461cc72097 (patch)
treef694d0cc0b9a1930dfc888462a282db5031f6b6e /replace_non_coprime_nums.py
parent01c6cf8af910f8e58ece342b45b22abcc8e498f4 (diff)
downloadleetcode-b7cd5b2d6cb9a619e68bc518a369b5461cc72097.tar.gz
leetcode-b7cd5b2d6cb9a619e68bc518a369b5461cc72097.zip
2197. replace non-coprime numbers in array
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]))