Replace Non-Coprime Numbers in Array

Hard
1409.

Replace Non-Coprime Numbers in Array

Replace Non-Coprime Numbers in Array is a hard coding problem on arrays, math and stack, asked in Amazon and Google interviews.

Two numbers are non-coprime when their greatest common divisor is greater than 1. Starting from nums, repeat the following while possible:

  1. Find any two adjacent numbers that are non-coprime.
  2. 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^5
  • 1 <= nums[i] <= 10^5
  • The values of the final array are at most 10^8.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var replaceNonCoprimes = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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:

  1. Find any two adjacent numbers that are non-coprime.
  2. 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^5
  • 1 <= nums[i] <= 10^5
  • The values of the final array are at most 10^8.

Hints for Replace Non-Coprime Numbers in Array

  1. Hint 1

    A merge can create a number that is non-coprime with what is to its left, so merges cascade backwards.

  2. Hint 2

    Process left to right with a stack holding an already fully merged prefix.

  3. Hint 3

    For each new value x, while the top of the stack shares a factor with x, pop it and set x = lcm(top, x); then push x.

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

  1. Create an empty stack.
  2. For each x in nums: while the stack is non-empty and gcd(top, x) > 1, pop top and set x = top / gcd(top, x) * x.
  3. Push x.
  4. 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 st

Java

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