Replace Non-Coprime Numbers in Array
You are given an array of integers nums. Perform the following steps:
- Find any two adjacent numbers in
numsthat are non-coprime. - If no such numbers are found, stop the process.
- Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
- Repeat this process as long as you keep finding two adjacent non-coprime numbers.
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.
The test cases are generated such that the values in the final array are less than or equal to 10^8.
Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.
Example 1
Input
nums = [6,4,3,2,7,6,2]Output
[12,7,6]After repeatedly replacing adjacent non-coprime pairs such as (6, 4), then (12, 3), then (12, 2), and finally (6, 2), no adjacent non-coprime numbers remain, so the final array is [12, 7, 6].
Example 2
Input
nums = [2,2,1,1,3,3,3]Output
[2,1,1,3]After replacing the adjacent non-coprime pairs (3, 3), then (3, 3), and then (2, 2), no adjacent non-coprime numbers remain, so the final array is [2, 1, 1, 3].
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
- The test cases are generated such that the values in the final array are less than or equal to 10^8.