Replace Non-Coprime Numbers in Array — Problem & Solution
Replace Non-Coprime Numbers in Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Replace Non-Coprime Numbers in Array is a hard coding problem on arrays, math and stack, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Math, Stack, Number Theory
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two numbers are non-coprime when their greatest common divisor is greater than 1. Starting from nums, repeat the following while possible:
- Find any two adjacent numbers that are non-coprime.
- Replace the pair by a single number: their least common multiple (LCM).
Return the final array. It can be shown that the order in which pairs are merged does not change the result. The test data guarantees that every value in the final array is at most 10^8.
Example 1
Input: nums = [4,6,5,15,7]
Output: [60,7]
Explanation: 4 and 6 merge into 12, 5 and 15 into 15, then 12 and 15 into 60; 60 and 7 are coprime.
Example 2
Input: nums = [3,3,1,1,2,4]
Output: [3,1,1,4]
Explanation: 1 is coprime with everything, so it separates its neighbours.
Example 3
Input: nums = [7]
Output: [7]
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^5The values of the final array are at most 10^8.
Hints for Replace Non-Coprime Numbers in Array
Hint 1
A merge can create a number that is non-coprime with what is to its left, so merges cascade backwards.
Hint 2
Process left to right with a stack holding an already fully merged prefix.
Hint 3
For each new value
x, while the top of the stack shares a factor withx, pop it and setx = lcm(top, x); then pushx.
How to solve Replace Non-Coprime Numbers in Array
Keep the processed prefix fully merged on a stack. A new number can only interact with the top, and every merge produces a number that may now interact with the new top — so merging continues down the stack until it meets a coprime neighbour.
Approach
- Create an empty stack.
- For each
xinnums: while the stack is non-empty andgcd(top, x) > 1, poptopand setx = top / gcd(top, x) * x. - Push
x. - Return the stack from bottom to top.
Why it works
Invariant: adjacent stack entries are coprime. Merging only grows the set of prime factors of a value, so an entry coprime with its neighbours could become non-coprime only through a merge involving that neighbour — which is exactly what the inner loop checks. When the loop stops, the new x is coprime with the top and the invariant holds again. At the end no adjacent pair is non-coprime, and since the final result does not depend on the merge order, this is the answer.
Complexity
- Time —
O(n log V) — each element is pushed and popped once, with a gcd per pop - Space —
O(n)
Pitfalls
- Checking only the incoming neighbour once misses cascades such as
[12, 5, 15]→[60]. - Compute the LCM as
a / gcd * b, dividing first, so intermediate products do not overflow. - 1 is coprime with everything (gcd 1), including another 1.
Reference solution
Python
from typing import List
from math import gcd
def replaceNonCoprimes(nums: List[int]) -> List[int]:
st = []
for x in nums:
while st and gcd(st[-1], x) > 1:
top = st.pop()
x = top // gcd(top, x) * x
st.append(x)
return stJava
private static long gcdOfTwo(long a, long b) {
while (b != 0) { long t = a % b; a = b; b = t; }
return a;
}
public static int[] replaceNonCoprimes(int[] nums) {
long[] st = new long[nums.length];
int top = 0;
for (int v : nums) {
long x = v;
while (top > 0) {
long g = gcdOfTwo(st[top - 1], x);
if (g == 1) break;
x = st[--top] / g * x;
}
st[top++] = x;
}
int[] res = new int[top];
for (int i = 0; i < top; i++) res[i] = (int) st[i];
return res;
}C++
long long gcdOfTwo(long long a, long long b) {
while (b != 0) { long long t = a % b; a = b; b = t; }
return a;
}
vector<int> replaceNonCoprimes(vector<int>& nums) {
vector<long long> st;
for (int v : nums) {
long long x = v;
while (!st.empty()) {
long long g = gcdOfTwo(st.back(), x);
if (g == 1) break;
x = st.back() / g * x;
st.pop_back();
}
st.push_back(x);
}
return vector<int>(st.begin(), st.end());
}JavaScript
var replaceNonCoprimes = function(nums) {
var gcd = function(a, b) {
while (b !== 0) { var t = a % b; a = b; b = t; }
return a;
};
var st = [];
for (var i = 0; i < nums.length; i++) {
var x = nums[i];
while (st.length > 0) {
var g = gcd(st[st.length - 1], x);
if (g === 1) break;
x = st.pop() / g * x;
}
st.push(x);
}
return st;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure