1
class Solution {
2
  public List<String> simplifiedFractions(int n) {
3
    List<String> list = new ArrayList<>();
4

5
    for (int numerator = 1; numerator < n; numerator++) {
6
      for (int denominator = numerator + 1; denominator <= n; denominator++) {
7
        if (gcd(numerator, denominator) == 1) {
8
          list.add(numerator + "/" + denominator);
9
          // System.out.println(numerator+"/"+denominator);
10
        }
11
      }
12
    }
13
    return list;
14
  }
15

16
  static int gcd(int a, int b) {
17
    // euclidean algo
18

19
    if (a == 0) {
20
      return b;
21
    }
22
    return gcd(b % a, a);
23
  }
24
}