-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
32 lines (31 loc) · 732 Bytes
/
Solution.cs
File metadata and controls
32 lines (31 loc) · 732 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution
{
public IList<int> ReplaceNonCoprimes(int[] nums)
{
int n = nums.Length;
Stack<int> stack = [];
for (int i = 0; i < n; i++)
{
int num = nums[i];
while (stack.Count > 0)
{
int gcd = Gcd(stack.Peek(), num);
if (gcd == 1) break;
num = (int)(1L * num * stack.Pop() / gcd);
}
stack.Push(num);
}
List<int> ans = [];
while (stack.Count > 0)
{
ans.Add(stack.Pop());
}
ans.Reverse();
return ans;
}
int Gcd(int a, int b)
{
if (b == 0) return a;
return Gcd(b, a % b);
}
}