Replace Non-Coprime Numbers in Array

Replace Non-Coprime Numbers in Array

What is this problem about?

The Replace Non-Coprime Numbers in Array interview question gives you an integer array and asks you to repeatedly merge adjacent elements that are not coprime (i.e., their GCD is greater than 1) by replacing them with their LCM, until no two adjacent elements share a common factor greater than 1. The array is processed from left to right, but merges can cascade when a new LCM is not coprime with the element before it.

Why is this asked in interviews?

This HARD problem is asked at Uber and Amazon because it combines number theory (GCD/LCM), stack-based processing, and greedy cascade thinking. It tests whether candidates can identify that merging adjacent elements may create new non-coprime pairs with earlier elements, requiring a stack to efficiently handle cascading merges. It mirrors problems in data stream aggregation and recursive merging systems.

Algorithmic pattern used

The pattern is stack simulation with GCD/LCM arithmetic. Use a stack. For each number in the array: push it onto the stack. Then, while the stack has at least two elements and the top two elements are not coprime (gcd(top, second) > 1), pop both, compute their LCM, and push the LCM back. The LCM of two numbers a and b is a * b // gcd(a, b). Repeat until no adjacent pair on the stack shares a factor. The final stack content is the answer.

Example explanation

Array: [6, 4, 3, 2, 7, 1]

• Push 6. Stack: [6]
• Push 4. gcd(6,4)=2 > 1 → LCM(6,4)=12. Pop both, push 12. Stack: [12]
• Push 3. gcd(12,3)=3 > 1 → LCM(12,3)=12. Merge → stack: [12]
• Push 2. gcd(12,2)=2 > 1 → LCM(12,2)=12. Merge → stack: [12]
• Push 7. gcd(12,7)=1 → coprime, stop. Stack: [12, 7]
• Push 1. gcd(7,1)=1 → coprime. Stack: [12, 7, 1]

Result: [12, 7, 1].

Common mistakes candidates make

• Processing only adjacent pairs once without the cascading inner loop, missing merges that occur after LCM replacements.
• Using GCD incorrectly — remember, non-coprime means gcd > 1, not gcd > 0.
• Computing LCM with overflow — use a // gcd(a,b) * b order to reduce overflow risk.
• Not using a stack, attempting in-place array modifications that miss cascades.

Interview preparation tip

For the Replace Non-Coprime Numbers in Array coding problem, the stack and number theory interview pattern is the key. The stack naturally handles cascading merges. Practice computing GCD and LCM quickly, and understand why a // gcd(a,b) * b is safer than a * b // gcd(a,b) for avoiding overflow. Amazon interviewers appreciate when you immediately identify the cascading nature of merges as the reason a stack is needed.