1447. Simplified Fractions LeetCode Solution

In this guide, you will get 1447. Simplified Fractions LeetCode Solution with the best time and space complexity. The solution to Simplified Fractions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Simplified Fractions solution in C++
4. Simplified Fractions solution in Java
5. Simplified Fractions solution in Python
6. Additional Resources

Problem Statement of Simplified Fractions

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. You can return the answer in any order.

Example 1:

Input: n = 2
Output: [“1/2”]
Explanation: “1/2” is the only unique fraction with a denominator less-than-or-equal-to 2.

Example 2:

Input: n = 3
Output: [“1/2″,”1/3″,”2/3”]

Example 3:

Input: n = 4
Output: [“1/2″,”1/3″,”1/4″,”2/3″,”3/4”]
Explanation: “2/4” is not a simplified fraction because it can be simplified to “1/2”.

Constraints:

1 <= n <= 100

Complexity Analysis

• Time Complexity: O(n^2\log n)
• Space Complexity: O(n^2)

1447. Simplified Fractions LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

1447. Simplified Fractions LeetCode Solution in Java

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);
  }
}
// code provided by PROGIEZ

1447. Simplified Fractions LeetCode Solution in Python

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
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.