Replace Non-Coprime Numbers in Array
HardPrompt
You are given an array of integers nums. Perform the following steps:
- Find any two adjacent numbers in
numsthat 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 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] <= 105- The test cases are generated such that the values in the final array are less than or equal to
108.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It uses a dynamic list to store the numbers. In a loop, it scans the list for any adjacent non-coprime pair. If found, it replaces them with their LCM and restarts the scan from the beginning of the now-modified list. This continues until a full scan finds no non-coprime pairs.
Algorithm
- Convert the input array
numsto aList<Integer>. - Start an outer loop
while(true). - Initialize a boolean
mergedInPass = false. - Start an inner loop to iterate from
i = 0tolist.size() - 2. - Get adjacent numbers
a = list.get(i)andb = list.get(i+1). - Calculate
g = GCD(a, b). - If
g > 1:- Calculate
l = LCM(a, b). - Remove elements at
iandi+1. - Insert
lat indexi. - Set
mergedInPass = true. breakthe inner loop.
- Calculate
- If
mergedInPassisfalseafter the inner loop,breakthe outer loop. - Return the final list.
Walkthrough
The algorithm maintains the array of numbers in a data structure that allows for efficient removal and insertion, such as Java's ArrayList. It enters a primary while loop that continues as long as modifications are being made to the list. A boolean flag, say merged, can track this. Inside the loop, merged is reset to false, and a for loop iterates through the current list to find an adjacent non-coprime pair (list.get(i), list.get(i+1)). To check for non-coprimality, we compute GCD(a, b). If GCD > 1, the numbers are non-coprime. Upon finding such a pair, we calculate their LCM. The two numbers are removed from the list, and their LCM is inserted at the position of the first number. The merged flag is set to true, and we break the inner for loop to restart the scan from the beginning of the updated list. This is crucial because the new LCM might be non-coprime with its new left neighbor. If the inner for loop completes without finding any non-coprime pairs (merged remains false), the main while loop terminates. The final list is then returned.
import java.util.ArrayList;import java.util.List;import java.util.stream.Collectors;import java.util.Arrays; class Solution { public List<Integer> replaceNonCoprimes(int[] nums) { List<Long> list = new ArrayList<>(); for (int num : nums) { list.add((long) num); } while (true) { boolean mergedInPass = false; for (int i = 0; i < list.size() - 1; i++) { long a = list.get(i); long b = list.get(i + 1); long commonDivisor = gcd(a, b); if (commonDivisor > 1) { list.remove(i + 1); list.set(i, lcm(a, b, commonDivisor)); mergedInPass = true; break; // Restart scan } } if (!mergedInPass) { break; } } return list.stream().map(Long::intValue).collect(Collectors.toList()); } private long gcd(long a, long b) { while (b != 0) { long temp = b; b = a % b; a = temp; } return a; } private long lcm(long a, long b, long gcd) { return (a / gcd) * b; }}Complexity
Time
O(N^3). In the worst case, we might perform O(N) merges. Each merge could require a scan of up to O(N) elements. The list modification itself takes O(N). So, one pass that results in a merge takes O(N^2). With O(N) merges, this leads to O(N^3). The O(log M) factor for GCD is dominated.
Space
O(N) to store the list of numbers.
Trade-offs
Pros
Simple to understand and directly follows the problem description.
Cons
Highly inefficient due to repeated scanning from the beginning after every merge.
Modifying a list (like
ArrayList) by removing and inserting elements in the middle is a slow operation (O(N)).
This is an optimization over the brute-force approach. Instead of restarting the scan from the beginning after a merge, we only backtrack one step. When two numbers at indices i-1 and i are merged, the new LCM is placed at i-1. This new number might be non-coprime with the element at i-2. So, we just need to move our check pointer i back one position to handle this potential new merge.
Algorithm
- Convert the input array
numsto aList<Long>to handle intermediate LCM values. - Initialize an index
i = 1. while (i < list.size()):- Get
a = list.get(i-1)andb = list.get(i). - Calculate
g = GCD(a, b). - If
g > 1:- Calculate
l = LCM(a, b). - Set
list.set(i-1, l). - Remove element at
iusinglist.remove(i). - If
i > 1, decrementi(i--).
- Calculate
- Else (
g == 1):- Increment
i(i++).
- Increment
- Get
- Return the final list.
Walkthrough
This method also uses a dynamic list like ArrayList. It iterates through the list with a single pointer i, starting from 1. At each position i, it checks the pair (list.get(i-1), list.get(i)). If they are non-coprime (GCD > 1), it calculates their LCM, replaces the element at i-1 with the LCM, and removes the element at i. Crucially, it then decrements the pointer i. If i was 1, it becomes 0, and the loop condition i < list.size() will re-evaluate. The next iteration will start with i=1 again, effectively re-checking from the start of the modified section. If i > 1, it becomes i-1, so the next check will be between the new LCM and its new left neighbor. If the numbers are coprime, we simply increment i to move to the next pair. The process continues until i traverses the entire list.
import java.util.ArrayList;import java.util.List;import java.util.stream.Collectors;import java.util.Arrays; class Solution { public List<Integer> replaceNonCoprimes(int[] nums) { List<Long> list = new ArrayList<>(); for (int num : nums) { list.add((long) num); } int i = 1; while (i < list.size()) { long a = list.get(i - 1); long b = list.get(i); long commonDivisor = gcd(a, b); if (commonDivisor > 1) { list.set(i - 1, lcm(a, b, commonDivisor)); list.remove(i); if (i > 1) { i--; // Backtrack to check with the previous element } } else { i++; } } return list.stream().map(Long::intValue).collect(Collectors.toList()); } private long gcd(long a, long b) { while (b != 0) { long temp = b; b = a % b; a = temp; } return a; } private long lcm(long a, long b, long gcd) { return (a / gcd) * b; }}Complexity
Time
O(N^2). The main loop pointer `i` makes N forward moves in total and can make O(N) backward moves. So the loop runs O(N) times. Inside the loop, `list.remove(i)` can take O(N) time in the worst case. This results in a total time complexity of O(N^2). The O(log M) factor for GCD is dominated.
Space
O(N) to store the list.
Trade-offs
Pros
More efficient than full rescanning as it avoids redundant checks on parts of the array that haven't changed.
Cons
Still suffers from the O(N) cost of element removal in an
ArrayList, leading to a quadratic time complexity.
This is the most efficient approach. It rephrases the problem in a way that is perfectly suited for a stack data structure. We process the input numbers one by one. Each new number is conceptually 'pushed' onto a result stack. Then, we repeatedly check if the top two elements of the stack are non-coprime. If they are, we 'pop' them, compute their LCM, and 'push' the result back. This continues until the top two are coprime or the stack has fewer than two elements.
Algorithm
- Initialize an empty list,
res, to be used as a stack. - For each
numin the input arraynums:- Add
numto the end ofres. while (res.size() > 1):- Get the last two elements:
y = res.get(res.size()-1)andx = res.get(res.size()-2). - Calculate
g = GCD(x, y). - If
g > 1:- Remove the last two elements from
res. - Calculate
l = LCM(x, y). - Add
lto the end ofres.
- Remove the last two elements from
- Else (
g == 1):breakthewhileloop.
- Get the last two elements:
- Add
- Return
res.
Walkthrough
The core idea is that when we add a new number, it only needs to be checked against its most recent predecessor. If they merge, the resulting new number needs to be checked against its most recent predecessor, and so on. This 'last-in, first-out' pattern of interaction is the hallmark of a stack. We can use an ArrayList or a LinkedList to act as a stack, as we only need efficient access to the end of the list. We iterate through each number num from the input array nums. For each num, we add it to our result list. Then, we enter a while loop that runs as long as the result list has at least two elements and the last two elements are non-coprime. Inside the while loop, we remove the last two elements (a and b), calculate their LCM, and add the LCM back to the end of the list. This process ensures that any non-coprime chain reaction is fully resolved before moving to the next number from the input array. After iterating through all numbers in nums, the result list holds the final sequence.
import java.util.ArrayList;import java.util.List;import java.util.LinkedList; class Solution { public List<Integer> replaceNonCoprimes(int[] nums) { LinkedList<Long> res = new LinkedList<>(); for (int num : nums) { long currentNum = num; while (!res.isEmpty()) { long prevNum = res.getLast(); long commonDivisor = gcd(prevNum, currentNum); if (commonDivisor > 1) { currentNum = lcm(prevNum, currentNum, commonDivisor); res.removeLast(); } else { break; } } res.add(currentNum); } List<Integer> finalList = new ArrayList<>(); for (long val : res) { finalList.add((int) val); } return finalList; } private long gcd(long a, long b) { while (b != 0) { long temp = b; b = a % b; a = temp; } return a; } private long lcm(long a, long b, long gcd) { return (a / gcd) * b; }}Complexity
Time
O(N * log M). Each of the N numbers is processed once. For each number, it might trigger a chain of merges with elements already in the stack. However, each merge operation reduces the size of the stack by one. In total, there are N pushes and at most N-1 merges. Each operation involves a GCD calculation, which takes O(log M), where M is the maximum possible value. Thus, the total time is dominated by the GCD calculations.
Space
O(N) in the worst case (if all numbers are pairwise coprime), the result list will store all N numbers.
Trade-offs
Pros
Optimal time complexity.
Each number is pushed onto the stack once. The total number of merge operations is bounded by N.
Operations at the end of an
ArrayListorLinkedList(add, remove last) are amortized O(1).
Cons
The logic is slightly less direct than a straightforward simulation, but it's a standard and powerful pattern.
Solutions
Solution
class Solution {public List<Integer> replaceNonCoprimes(int[] nums) { List<Integer> stk = new ArrayList<>(); for (int x : nums) { stk.add(x); while (stk.size() > 1) { x = stk.get(stk.size() - 1); int y = stk.get(stk.size() - 2); int g = gcd(x, y); if (g == 1) { break; } stk.remove(stk.size() - 1); stk.set(stk.size() - 1, (int)((long)x * y / g)); } } return stk; }private int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); }}class Solution {public: vector<int> replaceNonCoprimes(vector<int> &nums) { vector<int> stk; for (int x : nums) { stk.push_back(x); while (stk.size() > 1) { x = stk.back(); int y = stk[stk.size() - 2]; int g = __gcd(x, y); if (g == 1) { break; } stk.pop_back(); stk.back() = 1LL * x * y / g; } } return stk; }};class Solution: def replaceNonCoprimes(self, nums: List[int]) -> List[int]: stk = [] for x in nums: stk . append(x) while len(stk) > 1: x, y = stk[- 2:] g = gcd(x, y) if g == 1: break stk . pop() stk[- 1] = x * y // g return stkVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.