C C++ GCD LCM解Leetcode難題2197 Replace Non Coprime Numbers in Array[含Py3 code]

C C++ GCD LCM解Leetcode難題2197  Replace Non Coprime Numbers in Array

用binary Euclidean algorithm定義gcd，然後定義lcm之後就是用stack

[Py3 code請進]

-----

Use the binary Euclidean algorithm to define GCD, then define LCM and then use a stack.

[codes on Leetcode]https://leetcode.com/problems/replace-non-coprime-numbers-in-array/solutions/7194484/lcm-stack-reuse-nums-beats-100/

[Number theory playlist]https://www.youtube.com/watch?v=3FUyGjH_FZ0&list=PLYRlUBnWnd5Ld53SovfXQROVMAI_La2dv

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        top=-1
        for x in nums:
            cur=x
            while top!=-1:
                g=gcd(nums[top], cur)
                if g==1: break
                cur=nums[top]//g*cur
                top-=1
            top+=1
            nums[top]=cur
        return nums[:top+1]