1
class Solution {
2
  public List<Integer> replaceNonCoprimes(int[] nums) {
3
    List<Integer> al = new ArrayList<>();
4
    long n1 = nums[0];
5
    int idx = 1;
6

7
    while (idx < nums.length) {
8
      if ((int) gcd(n1, nums[idx]) == 1) {
9
        while (al.size() != 0) {
10
          int t = al.get(al.size() - 1);
11
          if (gcd(n1, t) == 1) break;
12
          else {
13
            al.remove(al.size() - 1);
14
            n1 = lcm(t, n1);
15
          }
16
        }
17

18
        al.add((int) n1);
19
        n1 = nums[idx];
20
        idx++;
21
      } else {
22
        n1 = lcm(n1, nums[idx]);
23
        idx++;
24
      }
25
    }
26

27
    while (al.size() != 0) {
28
      int t = al.get(al.size() - 1);
29
      if (gcd(n1, t) == 1) break;
30
      else {
31
        al.remove(al.size() - 1);
32
        n1 = lcm(t, n1);
33
      }
34
    }
35
    al.add((int) n1);
36

37
    return al;
38
  }
39

40
  public long gcd(long a, long b) {
41
    if (b == 0) return a;
42

43
    return gcd(b, a % b);
44
  }
45

46
  public long lcm(long a, long b) {
47
    long hcf = gcd(a, b);
48
    return (a * b) / hcf;
49
  }
50
}