2197. Replace Non-Coprime Numbers in Array LeetCode Solution

Last updated: February 26, 2025

In this guide, you will get 2197. Replace Non-Coprime Numbers in Array LeetCode Solution with the best time and space complexity. The solution to Replace Non-Coprime Numbers in Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Replace Non-Coprime Numbers in Array solution in C++
Replace Non-Coprime Numbers in Array solution in Java
Replace Non-Coprime Numbers in Array solution in Python
Additional Resources

2197. Replace Non-Coprime Numbers in Array LeetCode Solution image

Problem Statement of Replace Non-Coprime Numbers in Array

You are given an array of integers nums. Perform the following steps:

Find any two adjacent numbers in nums that 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 108.
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]
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.

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 105
The test cases are generated such that the values in the final array are less than or equal to 108.

Complexity Analysis

Time Complexity: O(n\log 10^8)
Space Complexity: O(n)

2197. Replace Non-Coprime Numbers in Array LeetCode Solution in C++

class Solution {
 public:
  vector<int> replaceNonCoprimes(vector<int>& nums) {
    vector<int> ans;

    for (int num : nums) {
      while (!ans.empty() && std::gcd(ans.back(), num) > 1)
        num = std::lcm(ans.back(), num), ans.pop_back();
      ans.push_back(num);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2197. Replace Non-Coprime Numbers in Array LeetCode Solution in Java

class Solution {
  public List<Integer> replaceNonCoprimes(int[] nums) {
    LinkedList<Integer> ans = new LinkedList<>();

    for (int num : nums) {
      while (!ans.isEmpty() && gcd(ans.getLast(), num) > 1)
        num = lcm(ans.removeLast(), num);
      ans.addLast(num);
    }

    return ans;
  }

  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));
  }
}
// code provided by PROGIEZ

2197. Replace Non-Coprime Numbers in Array LeetCode Solution in Python

class Solution:
  def replaceNonCoprimes(self, nums: list[int]) -> list[int]:
    ans = []

    for num in nums:
      while ans and math.gcd(ans[-1], num) > 1:
        num = math.lcm(ans.pop(), num)
      ans.append(num)

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents