aboutsummaryrefslogtreecommitdiff
path: root/replace_non_coprime_nums.py
blob: 8707c8daae4dd82cd0c32889ecbe4d3befb6681b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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]))