Skip to main content
Talentd

Replace Non-Coprime Numbers in Array - Solution & Explanation

HardArrayMathStackNumber Theory17 min readAsked at: Amazon, Microsoft, Uber +2
Practice this problem

Problem Statement

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.

Approach Overview

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 1: Brute Force Approach

This basic solution involves iterating through the list repeatedly to check if any two adjacent elements are non-coprime. If found, we replace them with their LCM and continue. We keep scanning and modifying the list until no such pairs are found. Though straightforward, this approach may be inefficient due to repeated scans of the list as elements change.

We define two functions: gcd (from the Python standard library) to find the Greatest Common Divisor and lcm to compute the Least Common Multiple. The main function, replace_non_coprimes, uses a while loop to traverse the list. Whenever adjacent non-coprime numbers are found, they are replaced with their LCM and the subsequent element is removed. The index i is adjusted to ensure all potential pairs are evaluated. This continues until no modifications are required.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n^2), due to repeated list scanning and modification.
Space Complexity: O(1), as alterations are in-place.

Try this approach in the editor →

Approach 2: Stack-Based Approach

Utilizing a stack data structure can effectively manage the merging process when working with adjacent non-coprime numbers. By pushing elements onto a stack, we can consistently assess the conditions for non-coprimality, merging elements as we identify them and leveraging the stack's Last-In-First-Out (LIFO) nature to efficiently manage remaining elements.

The Java solution employs a stack to hold elements as we iterate through the array. If the peek of the stack and the current number are non-coprime, we repeatedly pop and merge them until coprime pairs appear. This ensures minimal temporal space and logical quandaries, especially as the stack's nature facilitates the arbitrary order nature of the operation.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n), each element is pushed/popped from the stack a limited number of times.
Space Complexity: O(n), in the worst case, all elements may reside in the stack.

Try this approach in the editor →

Approach 3: Stack

If there exist three adjacent numbers x, y, z that can be merged, then the result of first merging x and y, then merging z, is the same as the result of first merging y and z, then merging x. Both results are LCM(x, y, z).

Therefore, we can always prefer to merge the adjacent numbers on the left, and then merge the result with the adjacent number on the right.

We use a stack to simulate this process. We traverse the array, and for each number, we push it into the stack. Then we continuously check whether the top two numbers of the stack are coprime. If they are not coprime, we pop these two numbers out of the stack, and then push their least common multiple into the stack, until the top two numbers of the stack are coprime, or there are less than two elements in the stack.

The final elements in the stack are the final result.

The time complexity is O(n times log M), and the space complexity is O(n). Where M is the maximum value in the array.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^2), due to repeated list scanning and modification.
Space Complexity: O(1), as alterations are in-place.

Stack-Based Approach

Time Complexity: O(n), each element is pushed/popped from the stack a limited number of times.
Space Complexity: O(n), in the worst case, all elements may reside in the stack.

Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n^2 log M)O(n)Good for understanding the merge rule and quick prototypes
Stack-Based Merge with GCD/LCMO(n log M)O(n)Optimal solution for interviews and large inputs

Video Solution

Replace Non-Coprime Numbers in Array | Simple Intuition | Leetcode 2197 | codestorywithMIK • codestorywithMIK • 8,786 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Replace Non-Coprime Numbers in Array easy or hard?
LeetCode classifies this problem as Hard because it combines number theory with stack-based sequence processing. The difficulty comes from handling cascading merges efficiently without repeatedly rescanning the array.
Replace Non-Coprime Numbers in Array Python/Java solution
Python implementations typically simulate merges with a list acting as a stack and use math.gcd for coprime checks. Java or C++ versions follow the same stack logic using a Deque or vector. All versions compute LCM as (a * b) / gcd(a, b) and run in O(n log M) time.
How to solve Replace Non-Coprime Numbers in Array in O(n)?
Use a stack to track the current sequence. For each element, push it and repeatedly check the top two stack values. If their gcd is greater than 1, replace them with their LCM and continue merging. Although GCD operations add a log factor, the stack ensures each element is processed only a few times, giving near-linear behavior.
What is the best approach for Replace Non-Coprime Numbers in Array?
The best approach uses a stack with repeated GCD checks. Push numbers onto the stack and merge the top two whenever their gcd is greater than 1 by replacing them with their LCM. Continue merging until the top pair becomes coprime. This method processes each element a limited number of times and runs in O(n log M) time.
Is Replace Non-Coprime Numbers in Array asked at Google/Amazon/Meta?
Problems involving GCD, LCM, and stack-based merging appear frequently in interviews at companies like Google, Amazon, and Meta. Variants test number theory knowledge and the ability to recognize when a stack can efficiently handle cascading adjacent operations.
What data structure is used in Replace Non-Coprime Numbers in Array?
The optimal solution relies on a stack. The stack keeps the partially processed array and allows efficient merging with the previous element whenever a non-coprime pair appears. GCD and LCM calculations from number theory are used during each merge.
What is the time complexity of Replace Non-Coprime Numbers in Array?
The optimal stack-based solution runs in O(n log M), where n is the array length and M is the maximum number value. The log factor comes from GCD calculations. A naive simulation that repeatedly scans and merges adjacent elements can degrade to O(n^2 log M).

Ready to solve this problem?

Practice Replace Non-Coprime Numbers in Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Pairs of Interchangeable Rectangles

Next

Remove All Adjacent Duplicates in String II