#2197
Replace Non-Coprime Numbers in Array
expert · 1230 · lc hard +32 · verified · 57.7% accepted · 843 likes · top 53%
Description
You are given an integer array nums. Repeatedly perform the following:
- Find any two adjacent elements in nums that are non-coprime (their GCD > 1).
- If no such pair exists, stop.
- Otherwise, replace both with their LCM.
Two integers x and y are non-coprime if GCD(x, y) > 1.
Return the final array after all replacements. It can be shown that processing pairs in any order yields the same result.
The test cases guarantee that all final values are at most 108.
Example 1:
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].
- (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
- (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
- (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [12,7,6].
Note that there are other ways to obtain the same resultant array.
Example 2:
Input: nums = [2,2,1,1,3,3,3]
Output: [2,1,1,3]
Explanation:
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3].
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3].
- (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [2,1,1,3].
Note that there are other ways to obtain the same resultant array.
Code
1
2
3