From b7cd5b2d6cb9a619e68bc518a369b5461cc72097 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 15 Sep 2025 20:30:09 -0600 Subject: 2197. replace non-coprime numbers in array --- replace_non_coprime_nums.py | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100644 replace_non_coprime_nums.py (limited to 'replace_non_coprime_nums.py') 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])) -- cgit v1.2.3