How to Solve the "Replace Non-Coprime Numbers in Array" Problem (LeetCode 2197) – Beginner’s Guide with C++, JavaScript & Python Code

-

Arrays are one of the most fundamental data structures in programming. Problems involving arrays often require combining, comparing, or transforming elements in specific ways. In this article, we’ll walk through a problem that revolves around replacing adjacent numbers that are non-coprime with their LCM (Least Common Multiple).

We’ll explain the problem clearly, explore the mathematical concepts involved, show how to approach it, and implement solutions in C++, JavaScript, and Python. Additionally, we'll explain the time and space complexity in simple terms.

✅ Problem Explanation

You are given an array nums with integers. The task is to repeatedly find two adjacent numbers that are non-coprime, replace them with their LCM, and keep doing this until no such pair remains.

➤ What is GCD and LCM?

  • GCD (Greatest Common Divisor): The largest integer that divides both numbers.
  • LCM (Least Common Multiple): The smallest number that both integers can divide into.

➤ Non-Coprime Numbers?

Two numbers are non-coprime if their GCD is greater than 1.

✅ Example Walkthrough

Example Input: [6, 4, 3, 2, 7, 6, 2]

Step 1:
Check (6, 4) → GCD = 2 → non-coprime → LCM = 12 → Replace → [12, 3, 2, 7, 6, 2]

Step 2:
Check (12, 3) → GCD = 3 → non-coprime → LCM = 12 → Replace → [12, 2, 7, 6, 2]

Step 3:
Check (12, 2) → GCD = 2 → non-coprime → LCM = 12 → Replace → [12, 7, 6, 2]

Step 4:
Check (6, 2) → GCD = 2 → non-coprime → LCM = 6 → Replace → [12, 7, 6]

No more adjacent non-coprime numbers → Output: [12, 7, 6]

✅ Approach / Algorithm

  1. Use a stack to store the resulting elements.
  2. Iterate over each number in the array.
  3. Push the number into the stack.
  4. After each push, check the last two numbers in the stack:
    • If they are non-coprime, pop them, calculate their LCM, and push the LCM back into the stack.
    • Repeat this step until the last two numbers are coprime or there’s only one element.
  5. At the end, the stack will hold the result.


✅ C++ Code Example

#include <iostream>
#include <vector>
#include <numeric> // For gcd
using namespace std;

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> stack;
        
        for (int n : nums) {
            stack.push_back(n);
            int g;
            
            // Keep merging the last two if they're non-coprime
            while (stack.size() > 1 && (g = gcd(stack.back(), stack[stack.size() - 2])) != 1) {
                long long a = stack.back();
                long long b = stack[stack.size() - 2];
                stack.pop_back();
                stack.pop_back();
                stack.push_back((a * b) / g); // Calculate LCM
            }
        }
        
        return stack;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {6, 4, 3, 2, 7, 6, 2};
    vector<int> result = solution.replaceNonCoprimes(nums);
    
    for (int num : result)
        cout << num << " ";
    
    return 0;
}

✅ JavaScript Code Example

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

function replaceNonCoprimes(nums) {
    const stack = [];
    
    for (let n of nums) {
        stack.push(n);
        
        while (stack.length > 1) {
            const last = stack[stack.length - 1];
            const secondLast = stack[stack.length - 2];
            const g = gcd(last, secondLast);
            
            if (g === 1) break;
            
            stack.pop();
            stack.pop();
            stack.push((last * secondLast) / g);
        }
    }
    
    return stack;
}

// Example
const nums = [6, 4, 3, 2, 7, 6, 2];
console.log(replaceNonCoprimes(nums)); // Output: [12, 7, 6]

✅ Python Code Example

import math

def replaceNonCoprimes(nums):
    stack = []
    
    for n in nums:
        stack.append(n)
        
        while len(stack) > 1:
            a = stack[-1]
            b = stack[-2]
            g = math.gcd(a, b)
            
            if g == 1:
                break
            
            stack.pop()
            stack.pop()
            lcm = (a * b) // g
            stack.append(lcm)
    
    return stack

# Example usage
nums = [6, 4, 3, 2, 7, 6, 2]
print(replaceNonCoprimes(nums))  # Output: [12, 7, 6]

✅ Time Complexity Analysis

  • Worst-case time complexity: O(n log(max_value))
    • We iterate over all elements once → O(n)
    • For each element, we may merge multiple times, but the total number of merges across the whole process is bounded by O(n) because each merge reduces the number of elements.
    • Computing GCD takes O(log(max_value)) time.

✅ Space Complexity Analysis

  • Space complexity: O(n)
    • The stack stores at most n elements at any point.

✅ Key Takeaways

  • Using a stack helps manage adjacent elements efficiently.
  • GCD and LCM are essential mathematical tools in solving this problem.
  • The problem is not about the order of merging, as the final result is unique.
  • This is a great example of how mathematical properties and data structures work together to solve real-world problems.

This problem is an excellent way to learn about mathematical functions like GCD/LCM and data structures like stacks while improving problem-solving skills.

Feel free to practice with different inputs and see how the stack helps in dynamically solving the problem!

Comments

Post a Comment