Replace Non-Coprime Numbers in Array Interview Question for Amazon

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.

The test cases are generated such that the values in the final array are less than or equal to 10⁸.

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.

Example 1:

Input: nums = [6,4,3,2,7,6,2]
Output: [12,7,6]
Explanation: 
- (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
- (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
- (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
- (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [12,7,6].
Note that there are other ways to obtain the same resultant array.

Example 2:

Input: nums = [2,2,1,1,3,3,3]
Output: [2,1,1,3]
Explanation: 
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3].
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3].
- (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [2,1,1,3].
Note that there are other ways to obtain the same resultant array.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
The test cases are generated such that the values in the final array are less than or equal to 10⁸.

import math

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

def solve(nums):
    stack = []
    for num in nums:
        while stack and gcd(stack[-1], num) > 1:
            stack[-1] = lcm(stack[-1], num)
            num = stack.pop()
        stack.append(num)
    return stack

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

nums2 = [2, 2, 1, 1, 3, 3, 3]
print(solve(nums2))  # Output: [2, 1, 1, 3]

Explanation:

The code implements a function solve(nums) that takes a list of integers nums as input and returns the final modified array after repeatedly replacing adjacent non-coprime numbers with their LCM.

The core idea is to use a stack to keep track of the numbers processed so far. For each number in the input array, we check if it's non-coprime with the top element of the stack. If it is, we replace the top element of the stack with their LCM and repeat the process until the current number is coprime with the top of the stack or the stack is empty. Then, we push the current number onto the stack.

Here's a step-by-step breakdown:

gcd(a, b) function:
- Calculates the Greatest Common Divisor (GCD) of two numbers a and b using the Euclidean algorithm.
- The Euclidean algorithm is an efficient way to find the GCD. It repeatedly applies the modulo operator until the remainder is 0. The last non-zero remainder is the GCD.
lcm(a, b) function:
- Calculates the Least Common Multiple (LCM) of two numbers a and b using the formula: LCM(a, b) = (a * b) // GCD(a, b).
solve(nums) function:
- Initializes an empty stack stack.
- Iterates through each number num in the input array nums.
- While the stack is not empty and the GCD of the top element of the stack and the current number num is greater than 1 (i.e., they are non-coprime):
  - Replace the top element of the stack with the LCM of the top element and num:
    - stack[-1] = lcm(stack[-1], num)
  - num is then set to the value we just calculated, and pop the old stack[-1]
    - num = stack.pop()
- After the while loop, push the current number num onto the stack.
- Finally, return the stack, which contains the final modified array.

Example 1 walkthrough:

nums = [6, 4, 3, 2, 7, 6, 2]

num = 6, stack = []. Push 6. stack = [6]
num = 4, stack = [6]. gcd(6, 4) = 2 > 1. stack[-1] = lcm(6, 4) = 12. num = stack.pop() = 12. Push 12. stack = [12]
num = 3, stack = [12]. gcd(12, 3) = 3 > 1. stack[-1] = lcm(12, 3) = 12. num = stack.pop() = 12. Push 12. stack = [12]
num = 2, stack = [12]. gcd(12, 2) = 2 > 1. stack[-1] = lcm(12, 2) = 12. num = stack.pop() = 12. Push 12. stack = [12]
num = 7, stack = [12]. gcd(12,7) = 1. Push 7. stack = [12,7]
num = 6, stack = [12,7]. gcd(7,6) = 1. Push 6. stack = [12,7,6]
num = 2, stack = [12,7,6]. gcd(6,2) = 2 > 1. stack[-1] = lcm(6,2) = 6. num = stack.pop() = 6. Push 6. stack = [12,7,6]

Result: [12, 7, 6]

Example 2 walkthrough:

nums = [2, 2, 1, 1, 3, 3, 3]

num = 2, stack = []. Push 2. stack = [2]
num = 2, stack = [2]. gcd(2, 2) = 2 > 1. stack[-1] = lcm(2, 2) = 2. num = stack.pop() = 2. Push 2. stack = [2]
num = 1, stack = [2]. gcd(2, 1) = 1. Push 1. stack = [2, 1]
num = 1, stack = [2, 1]. gcd(1, 1) = 1. Push 1. stack = [2, 1, 1]
num = 3, stack = [2, 1, 1]. gcd(1, 3) = 1. Push 3. stack = [2, 1, 1, 3]
num = 3, stack = [2, 1, 1, 3]. gcd(3, 3) = 3 > 1. stack[-1] = lcm(3, 3) = 3. num = stack.pop() = 3. Push 3. stack = [2, 1, 1, 3]
num = 3, stack = [2, 1, 1, 3]. gcd(3, 3) = 3 > 1. stack[-1] = lcm(3, 3) = 3. num = stack.pop() = 3. Push 3. stack = [2, 1, 1, 3]

Result: [2, 1, 1, 3]

Time and Space Complexity:

Time Complexity: O(N * log(M)), where N is the length of the input array nums, and M is the maximum value in nums. The while loop inside the for loop can potentially iterate multiple times for each element in nums. In each iteration of the while loop, we calculate the GCD and LCM, both of which take logarithmic time with respect to the values involved (GCD using the Euclidean algorithm). In the worst case, an element could merge with all the previous elements, leading to a total runtime of O(N * log(M)), where M is the maximum value in the final array (which can be as large as 10^8).

Space Complexity: O(N), where N is the length of the input array nums. The stack stack can potentially store all the elements of nums in the worst case (when no two adjacent elements are non-coprime). Therefore, the space complexity is linear with respect to the size of the input array.