Watch 10 video solutions for Replace Non-Coprime Numbers in Array, a hard level problem involving Array, Math, Stack. This walkthrough by codestorywithMIK has 8,375 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of integers nums. Perform the following steps:
nums that are non-coprime.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 <= 1051 <= nums[i] <= 105108.Problem Overview: You receive an integer array. Whenever two adjacent numbers are not coprime (their gcd > 1), replace them with their lcm. Continue until every adjacent pair is coprime. The final array after all merges is the result.
Approach 1: Brute Force Simulation (O(n2 log M) time, O(n) space)
Directly simulate the process described in the problem. Iterate through the array and check adjacent elements using gcd(a, b). If the gcd is greater than 1, compute lcm(a, b) and replace the pair with the merged value. Because a merge can create new non‑coprime neighbors, restart the scan or step backward after each replacement.
This approach repeatedly scans the array and performs many shifts after merges, which leads to quadratic behavior in the worst case. It demonstrates the rule clearly but becomes slow when many cascading merges happen. Still useful for understanding the mechanics of repeated LCM replacement using number theory operations.
Approach 2: Stack-Based Merge (O(n log M) time, O(n) space)
Use a stack to maintain the current valid sequence. Iterate through the array and push each number. After pushing, check the top two values. If their gcd is greater than 1, pop them and push their lcm. Continue merging while the new top pair remains non‑coprime.
The key insight: each number only participates in a limited number of merges, so the total operations stay linear relative to the array length. The stack naturally handles chain reactions where one merge triggers another. This pattern is common when resolving adjacent constraints in stack-based processing of an array.
Recommended for interviews: The stack-based approach is the expected solution. It reduces repeated scans and handles cascading merges efficiently with amortized linear processing. Interviewers often want to see recognition that adjacent operations with possible backtracking are naturally solved with a stack. Mention the brute-force simulation first to show understanding, then optimize using the stack merge strategy.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2 log M) | O(n) | Good for understanding the merge rule and quick prototypes |
| Stack-Based Merge with GCD/LCM | O(n log M) | O(n) | Optimal solution for interviews and large inputs |