Replace Non-Coprime Numbers in Array

Challenge Points: 30

Level: Hard

You are given an array nums. You must repeatedly replace adjacent non-coprime numbers using the rule:

Find any two adjacent numbers whose GCD > 1
→ These numbers are non-coprime.
Remove both numbers.
Insert their LCM in the same position.
Repeat until no adjacent pair has GCD > 1.

The final array is guaranteed to be the same regardless of which valid pair you merge first.

The final values will always be ≤ 10⁸.

Definitions:
Two numbers x and y are non-coprime if:

GCD(x, y) > 1

Example 1:

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

Output: [12,7,6]

Explanation:

(6, 4) → merge → LCM(6,4)=12 → [12,3,2,7,6,2] (12, 3) → merge → 12 → [12,2,7,6,2] (12, 2) → merge → 12 → [12,7,6,2] (6, 2) → merge → 6 → [12,7,6] No more pairs → result is [12,7,6].