LeetCode 2197: Replace Non-Coprime Numbers in Array Solution
Master LeetCode problem 2197 (Replace Non-Coprime Numbers in Array), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
2197. Replace Non-Coprime Numbers in Array
Problem Explanation
Explanation
To solve this problem, we iterate through the array and check for adjacent numbers that are non-coprime. If we find such a pair, we replace them with their LCM and continue the process until no more non-coprime pairs are found. We can use the Euclidean algorithm to calculate the GCD of two numbers efficiently.
- Initialize a flag to track if any modifications were made in the current iteration.
- Iterate through the array and for each pair of adjacent numbers:
- If the GCD of the pair is greater than 1, replace them with their LCM and set the flag to true.
- Continue this process until no modifications are made in an iteration.
The time complexity of this approach is O(n * log(max(nums))) where n is the number of elements in the array and max(nums) represents the maximum value in the array.
Solution Code
import java.util.*;
class Solution {
public int[] replaceNonCoprimeNumbers(int[] nums) {
boolean modified = true;
while (modified) {
modified = false;
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < nums.length - 1 && gcd(nums[i], nums[i + 1]) > 1) {
temp.add(lcm(nums[i], nums[i + 1]));
i++;
modified = true;
} else {
temp.add(nums[i]);
}
}
nums = temp.stream().mapToInt(Integer::intValue).toArray();
}
return nums;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
private int lcm(int a, int b) {
return a * (b / gcd(a, b));
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 2197 (Replace Non-Coprime Numbers in Array)?
This page provides optimized solutions for LeetCode problem 2197 (Replace Non-Coprime Numbers in Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 2197 (Replace Non-Coprime Numbers in Array)?
The time complexity for LeetCode 2197 (Replace Non-Coprime Numbers in Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 2197 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2197 in Java, C++, or Python.