replace-non-coprime-numbers-in-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array of integers <code>nums</code>. Perform the following steps:

<ol>
	<li>Find any two adjacent numbers in <code>nums</code> that are non-coprime.</li>
	<li>If no such numbers are found, stop the process.</li>
	<li>Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).</li>
	<li>Repeat this process as long as you keep finding two adjacent non-coprime numbers.</li>
</ol>

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 <code>108</code>.

Two values <code>x</code> and <code>y</code> are non-coprime if <code>GCD(x, y) &gt; 1</code> where <code>GCD(x, y)</code> is the Greatest Common Divisor of <code>x</code> and <code>y</code>.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
	<li>The test cases are generated such that the values in the final array are less than or equal to <code>108</code>.</li>
</ul>

replaceNonCoprimes

Replace Non-Coprime Numbers in Array

Remove All Adjacent Duplicates in String II

remove-all-adjacent-duplicates-in-string-ii

删除字符串中的所有相邻重复项 II

Number of Pairs of Interchangeable Rectangles

number-of-pairs-of-interchangeable-rectangles

可互换矩形的组数

Split the Array to Make Coprime Products

split-the-array-to-make-coprime-products

分割数组使乘积互质

Stack

Array

Math

Number Theory

给你一个整数数组 <code>nums</code> 。请你对数组执行下述操作：

<ol>
	<li>从 <code>nums</code> 中找出 任意 两个 相邻 的 非互质 数。</li>
	<li>如果不存在这样的数，终止 这一过程。</li>
	<li>否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。</li>
	<li>只要还能找出两个相邻的非互质数就继续 重复 这一过程。</li>
</ol>

返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。

生成的测试用例可以保证最终数组中的值 小于或者等于 <code>108</code> 。

两个数字 <code>x</code> 和 <code>y</code> 满足 非互质数 的条件是：<code>GCD(x, y) &gt; 1</code> ，其中 <code>GCD(x, y)</code> 是 <code>x</code> 和 <code>y</code> 的 最大公约数 。

&nbsp;

示例 1 ：

<pre>
输入：nums = [6,4,3,2,7,6,2]
输出：[12,7,6]
解释：
- (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
- (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
- (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
现在，nums 中不存在相邻的非互质数。
因此，修改后得到的最终数组是 [12,7,6] 。
注意，存在其他方法可以获得相同的最终数组。
</pre>

示例 2 ：

<pre>
输入：nums = [2,2,1,1,3,3,3]
输出：[2,1,1,3]
解释：
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
- (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
现在，nums 中不存在相邻的非互质数。 
因此，修改后得到的最终数组是 [2,1,1,3] 。 
注意，存在其他方法可以获得相同的最终数组。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
	<li>生成的测试用例可以保证最终数组中的值 小于或者等于 <code>108</code> 。</li>
</ul>