Replace Non-Coprime Numbers in Array - Practice Coding Problems

Replace Non-Coprime Numbers in Array - Problem

You are given an array of integers nums. Perform the following steps:

Find any two adjacent numbers in nums that are non-coprime.
If no such numbers are found, stop the process.
Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
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.

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.

Input & Output

Example 1 — Basic Merging

$ Input: nums = [6,4,3,2,21]

› Output: [6,252]

💡 Note: Step by step: [6,4,3,2,21] → GCD(4,3)=1, GCD(3,2)=1, GCD(2,21)=1, no adjacent non-coprime pairs initially. However, after processing with stack: 4 and 3 can merge through cascading with later elements, resulting in [6,252].

Example 2 — Simple Case

$ Input: nums = [2,3,4]

› Output: [2,3,4]

💡 Note: GCD(2,3)=1 and GCD(3,4)=1, all pairs are coprime, so no merging occurs. Return original array.

Example 3 — Complete Merge

$ Input: nums = [4,6,15,35]

› Output: [420]

💡 Note: GCD(6,15)=3>1, merge to get [4,30,35]. Then GCD(4,30)=2>1, merge to get [60,35]. Finally GCD(60,35)=5>1, merge to get [420].

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶
The final array values are ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array with potential non-coprime adjacent pairs

Find & Merge

Identify GCD > 1 pairs and replace with LCM

Final Result

Array with no adjacent non-coprime pairs

Key Takeaway

🎯 Key Insight: Use a stack to efficiently handle cascading merges when processing non-coprime adjacent pairs

Asked in

G Google 15 f Meta 8 M Microsoft 6

The key insight is that adjacent non-coprime numbers (GCD > 1) must be merged into their LCM, and this process cascades. The optimal approach uses a stack to handle cascading merges efficiently in a single pass. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Approach	O(n)	O(n)	Use stack to efficiently handle cascading merges in single pass
Brute Force - Repeated Scanning	O(n²)	O(1)	Repeatedly scan array from left to right, merge first non-coprime pair found

Stack-Based Approach — Algorithm Steps

Step 1: Initialize empty stack
Step 2: For each element, try to merge with stack top
Step 3: Handle cascading merges until no more possible
Step 4: Return stack contents as result

Visualization

Tap to expand

Step-by-Step Walkthrough

Push to Stack

Add element if no merge possible

Check Merge

Compare with stack top using GCD

Cascading

Keep merging until no more possible

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return (a * b) / gcd(a, b);
}

int* solution(int* nums, int numsSize, int* returnSize) {
    long long stack[1000];
    int stackSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        long long current = nums[i];
        
        // Try to merge current with stack top
        while (stackSize > 0 && gcd(stack[stackSize - 1], current) > 1) {
            long long top = stack[stackSize - 1];
            stackSize--;
            current = lcm(top, current);
        }
        
        stack[stackSize++] = current;
    }
    
    int* result = (int*)malloc(stackSize * sizeof(int));
    for (int i = 0; i < stackSize; i++) {
        result[i] = (int)stack[i];
    }
    *returnSize = stackSize;
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array manually
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is pushed and popped at most once from stack

✓ Linear Growth

Space Complexity

O(n)

Stack can contain up to n elements in worst case

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler