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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Replace Non-Coprime Numbers in Array

Difficulty: Hard

Problem Description

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

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

Key Insights

  • Non-coprime numbers share a common divisor greater than 1.
  • The LCM of two numbers can be calculated using the formula: LCM(a, b) = (a * b) / GCD(a, b).
  • The process involves repeated modifications to the array until no adjacent non-coprime pairs remain.
  • A stack can be utilized to efficiently manage the merging of adjacent non-coprime numbers.

Space and Time Complexity

Time Complexity: O(n log(max(nums))) - where n is the length of the array and max(nums) is the maximum number in the array (due to GCD calculations). Space Complexity: O(n) - for the stack used to store the modified array.

Solution

To solve the problem, we will utilize a stack data structure to keep track of the numbers as we process the array. The algorithm will iterate through the input array, and for each number, we will check if it forms a non-coprime pair with the number on top of the stack. If it does, we will calculate the LCM of the two numbers, pop the top of the stack, and push the LCM back onto the stack. This process will continue until we have processed all numbers in the array. Finally, the stack will contain the final modified array.

Code Solutions

from math import gcd

def replaceNonCoprimeNumbers(nums):
    stack = []
    
    for num in nums:
        while stack and gcd(stack[-1], num) > 1:
            num = (stack.pop() * num) // gcd(stack[-1], num)
        stack.append(num)
    
    return stack
← Back to All Questions