Problem Statement in English

You’re given an array of integers nums. A pair of integers (a, b) is coprime if gcd(a, b) == 1, where gcd(a, b) is the greatest common divisor of a and b.

You need to repeatedly perform the following steps until no such pair of adjacent elements exists:

  1. Find the first pair of adjacent elements (a, b) in the array such that gcd(a, b) != 1.
  2. Replace the pair (a, b) with their LCM.
  3. Repeat the process from step 1.

Your task is to return the final array after all such replacements have been made.

Approach

To solve this problem, we can use a stack to keep track of the elements in the array.

We will iterate through each number in the nums array and for each number, we will check if it is coprime with the top element of the stack. If they are not coprime (i.e., their GCD is greater than 1), we will pop the top element from the stack, calculate the LCM of the two numbers, and push the LCM back onto the stack. We will continue this process until we have processed all elements in the nums array.

There is a handy formula to calculate LCM using GCD:

$\text{LCM}(a, b) = \frac{(a * b)}{\text{GCD}(a, b)}$


---

## Solution in Python

```python

class Solution(object):
    def replaceNonCoprimes(self, nums):
        stack = []

        for num in nums:
            while stack:
                g = gcd(stack[-1], num)
                if g == 1:
                    break
                num = (stack.pop() * num) // g
            stack.append(num)

        return stack

Complexity

  • Time: $O(n \log m)$, where $n$ is the length of the nums array and $m$ is the maximum element in the array (for GCD calculations).

  • Space: $O(n)$, for the stack used to store the elements.

Mistakes I Made

I didn’t know the handy formula :(

And we are done.