2197. Replace Non-Coprime Numbers in Array Hard

1/**
2 * [2197] Replace Non-Coprime Numbers in Array
3 *
4 * You are given an array of integers nums. Perform the following steps:
5 * <ol>
6 * 	Find any two adjacent numbers in nums that are non-coprime.
7 * 	If no such numbers are found, stop the process.
8 * 	Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
9 * 	Repeat this process as long as you keep finding two adjacent non-coprime numbers.
10 * </ol>
11 * 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.
12 * The test cases are generated such that the values in the final array are less than or equal to 10^8.
13 * 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.
14 *  
15 * Example 1:
16 * 
17 * Input: nums = [6,4,3,2,7,6,2]
18 * Output: [12,7,6]
19 * Explanation: 
20 * - (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [<u>12</u>,3,2,7,6,2].
21 * - (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [<u>12</u>,2,7,6,2].
22 * - (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [<u>12</u>,7,6,2].
23 * - (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,<u>6</u>].
24 * There are no more adjacent non-coprime numbers in nums.
25 * Thus, the final modified array is [12,7,6].
26 * Note that there are other ways to obtain the same resultant array.
27 * 
28 * Example 2:
29 * 
30 * Input: nums = [2,2,1,1,3,3,3]
31 * Output: [2,1,1,3]
32 * Explanation: 
33 * - (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,<u>3</u>,3].
34 * - (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,<u>3</u>].
35 * - (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [<u>2</u>,1,1,3].
36 * There are no more adjacent non-coprime numbers in nums.
37 * Thus, the final modified array is [2,1,1,3].
38 * Note that there are other ways to obtain the same resultant array.
39 * 
40 *  
41 * Constraints:
42 * 
43 * 	1 <= nums.length <= 10^5
44 * 	1 <= nums[i] <= 10^5
45 * 	The test cases are generated such that the values in the final array are less than or equal to 10^8.
46 * 
47 */
48pub struct Solution {}
49
50// problem: https://leetcode.com/problems/replace-non-coprime-numbers-in-array/
51// discuss: https://leetcode.com/problems/replace-non-coprime-numbers-in-array/discuss/?currentPage=1&orderBy=most_votes&query=
52
53// submission codes start here
54
55impl Solution {
56    pub fn replace_non_coprimes(nums: Vec<i32>) -> Vec<i32> {
57        vec![]
58    }
59}
60
61// submission codes end
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn test_2197() {
69    }
70}
71