{x}
blog image

Replace Non-Coprime Numbers in Array

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

  1. Find any two adjacent numbers in nums that are non-coprime.
  2. If no such numbers are found, stop the process.
  3. Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
  4. 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.

2197. Replace Non-Coprime Numbers in Array

Problem Description

Given an array of integers nums, repeatedly find any two adjacent numbers that are non-coprime (their greatest common divisor (GCD) is greater than 1), replace them with their least common multiple (LCM), and repeat until no such adjacent pairs exist. Return the final modified array.

Solution: Stack-based Approach

The core idea is to use a stack to efficiently manage the merging process. The observation that the order of merging non-coprime pairs doesn't affect the final result simplifies the algorithm. We can process the numbers from left to right, merging as we go.

Algorithm:

  1. Initialization: Start with an empty stack.
  2. Iteration: Iterate through the input array nums.
  3. Push: Push each number onto the stack.
  4. Check and Merge: After pushing, check the top two elements of the stack. If their GCD is greater than 1 (non-coprime), pop them, calculate their LCM, and push the LCM back onto the stack. Repeat this step until the top two elements are coprime or the stack has fewer than two elements.
  5. Result: The final contents of the stack represent the modified array.

Time Complexity: O(n log M), where n is the length of the input array and M is the maximum value in the array. The dominant factor is the GCD and LCM calculations, which typically have a logarithmic time complexity. In the worst case, we might perform these operations for each element.

Space Complexity: O(n) in the worst case, as the stack could potentially hold all elements of the input array.

Code Implementation (Python)

import math
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    return (a * b) // gcd(a, b)
 
def replaceNonCoprimes(nums):
    stack = []
    for num in nums:
        stack.append(num)
        while len(stack) >= 2:
            a = stack[-2]
            b = stack[-1]
            if gcd(a, b) > 1:
                stack.pop()
                stack.pop()
                stack.append(lcm(a, b))
            else:
                break
    return stack

Code Implementation (Java)

import java.util.*;
 
class Solution {
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
 
    private int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
 
    public List<Integer> replaceNonCoprimes(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        for (int num : nums) {
            stack.push(num);
            while (stack.size() >= 2) {
                int a = stack.get(stack.size() - 2);
                int b = stack.peek();
                if (gcd(a, b) > 1) {
                    stack.pop();
                    stack.pop();
                    stack.push(lcm(a, b));
                } else {
                    break;
                }
            }
        }
        return new ArrayList<>(stack);
    }
}

The implementations in other languages (C++, Go, TypeScript) would follow a similar structure, using their respective stack data structures and GCD/LCM functions. The core logic remains consistent across all languages.