We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Replace Non-Coprime Numbers in Array

Number: 2307

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given an array of integers, repeatedly find any two adjacent numbers that are non-coprime (i.e. their greatest common divisor is greater than 1) and replace them with their least common multiple (LCM). Continue this process until no such adjacent pair exists. The result is guaranteed to be unique regardless of the order of operations.

Key Insights

  • Use a stack to simulate merging adjacent non-coprime numbers.
  • Check the top of the stack with the current number and merge as long as they are non-coprime.
  • Merging is done by computing the LCM and then rechecking with the new top of the stack.
  • Euclid’s algorithm is used to compute the greatest common divisor (GCD).
  • The result is independent of the order of merging, which simplifies the solution.

Space and Time Complexity

Time Complexity: O(n * log(max(nums))) on average, since each merge operation involves computing GCD which takes logarithmic time. Space Complexity: O(n) for the stack storage.

Solution

The solution uses a stack-based approach. We iterate over the input array and for each number, we:

  1. Check the top of the stack to see if it is non-coprime with the current number.
  2. If they are non-coprime (GCD > 1), compute the LCM of these two numbers, pop the stack, and use the LCM as the new candidate.
  3. Continue merging with the new candidate until no adjacent non-coprime pair is found.
  4. Push the final candidate on the stack. This algorithm effectively simulates the replacement process, ensuring that only adjacent pairs are merged and handling cascaded merges correctly.

Code Solutions

# Import gcd from math module for computing greatest common divisor.
from math import gcd

def replaceNonCoprimes(nums):
    stack = []
    for num in nums:
        # For each number, try to merge with previous numbers if they are non-coprime.
        while stack and gcd(stack[-1], num) > 1:
            # Compute LCM using formula: lcm(a, b) = (a * b) // gcd(a, b)
            prev = stack.pop()
            num = (prev * num) // gcd(prev, num)
        # Push the current number (or merged value) onto the stack.
        stack.append(num)
    return stack

# Example usage:
# nums = [6,4,3,2,7,6,2]
# print(replaceNonCoprimes(nums))  # Expected output: [12,7,6]
← Back to All Questions