Skip to content

1447. Simplified Fractions 👍

  • Time: $O(n^2\log n)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  vector<string> simplifiedFractions(int n) {
    vector<string> ans;
    for (int denominator = 2; denominator <= n; ++denominator)
      for (int numerator = 1; numerator < denominator; ++numerator)
        if (__gcd(denominator, numerator) == 1)
          ans.push_back(to_string(numerator) + "/" + to_string(denominator));
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public List<String> simplifiedFractions(int n) {
    List<String> ans = new ArrayList<>();
    for (int denominator = 2; denominator <= n; ++denominator)
      for (int numerator = 1; numerator < denominator; ++numerator)
        if (gcd(denominator, numerator) == 1)
          ans.add(String.valueOf(numerator) + "/" + String.valueOf(denominator));
    return ans;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

1
2
3
4
5
6
7
8
class Solution:
  def simplifiedFractions(self, n: int) -> list[str]:
    ans = []
    for denominator in range(2, n + 1):
      for numerator in range(1, denominator):
        if math.gcd(denominator, numerator) == 1:
          ans.append(str(numerator) + '/' + str(denominator))
    return ans