You are given an array of integers nums. Perform the following steps:
nums that are non-coprime.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 108.
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 <= 1051 <= nums[i] <= 105108.This basic solution involves iterating through the list repeatedly to check if any two adjacent elements are non-coprime. If found, we replace them with their LCM and continue. We keep scanning and modifying the list until no such pairs are found. Though straightforward, this approach may be inefficient due to repeated scans of the list as elements change.
We define two functions: gcd (from the Python standard library) to find the Greatest Common Divisor and lcm to compute the Least Common Multiple. The main function, replace_non_coprimes, uses a while loop to traverse the list. Whenever adjacent non-coprime numbers are found, they are replaced with their LCM and the subsequent element is removed. The index i is adjusted to ensure all potential pairs are evaluated. This continues until no modifications are required.
JavaScript
Time Complexity: O(n^2), due to repeated list scanning and modification.
Space Complexity: O(1), as alterations are in-place.
Utilizing a stack data structure can effectively manage the merging process when working with adjacent non-coprime numbers. By pushing elements onto a stack, we can consistently assess the conditions for non-coprimality, merging elements as we identify them and leveraging the stack's Last-In-First-Out (LIFO) nature to efficiently manage remaining elements.
The Java solution employs a stack to hold elements as we iterate through the array. If the peek of the stack and the current number are non-coprime, we repeatedly pop and merge them until coprime pairs appear. This ensures minimal temporal space and logical quandaries, especially as the stack's nature facilitates the arbitrary order nature of the operation.
C++
Time Complexity: O(n), each element is pushed/popped from the stack a limited number of times.
Space Complexity: O(n), in the worst case, all elements may reside in the stack.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), due to repeated list scanning and modification. |
| Stack-Based Approach | Time Complexity: O(n), each element is pushed/popped from the stack a limited number of times. |
How to EASILY solve LeetCode problems • NeetCode • 427,724 views views
Watch 9 more video solutions →Practice Replace Non-Coprime Numbers in Array with our built-in code editor and test cases.
Practice on FleetCode