Replace Non-Coprime Numbers in Array — LeetCode 2197 Python Solution

The problem

You are given an array of integers nums. Perform the following steps: Find any two adjacent numbers in nums that are non-coprime.

Example

Input

nums = [6,4,3,2,7,6,2]

Output

[12,7,6]

Explanation

- (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].

Python solution

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        stk = []
        for x in nums:
            stk.append(x)
            while len(stk) > 1:
                x, y = stk[-2:]
                g = gcd(x, y)
                if g == 1:
                    break
                stk.pop()
                stk[-1] = x * y // g
        return stk

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2197. Replace Non-Coprime Numbers in Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems