Simplified Fractions
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through all possible numerators and denominators and checks if they form a simplified fraction by calculating their Greatest Common Divisor (GCD).
Algorithm
-
- Initialize an empty list
resultto store the fraction strings.
- Initialize an empty list
-
- Iterate through all possible denominators
dfrom2ton.
- Iterate through all possible denominators
-
- For each
d, iterate through all possible numeratorsnumfrom1tod-1.
- For each
-
- Calculate the greatest common divisor (GCD) of
numanddusing a helper function (e.g., Euclidean algorithm).
- Calculate the greatest common divisor (GCD) of
-
- If
gcd(num, d) == 1, the fraction is simplified. Add the stringnum + "/" + dto theresultlist.
- If
-
- After all loops complete, return the
resultlist.
- After all loops complete, return the
Walkthrough
We can generate all possible fractions where the denominator d is between 2 and n, and the numerator num is between 1 and d-1.
A fraction num/d is considered "simplified" if its numerator and denominator are coprime, meaning their greatest common divisor (GCD) is 1.
The algorithm involves two nested loops to iterate through all (num, d) pairs. Inside the loops, we use a helper function to calculate gcd(num, d). The most common and efficient way to compute GCD is the Euclidean algorithm.
If gcd(num, d) equals 1, we format the pair as a string "num/d" and add it to our result list.
This method is straightforward to understand and implement but is not the most optimal due to the overhead of calculating GCD for every pair.
import java.util.ArrayList;import java.util.List; class Solution { public List<String> simplifiedFractions(int n) { List<String> result = new ArrayList<>(); if (n < 2) { return result; } for (int denominator = 2; denominator <= n; denominator++) { for (int numerator = 1; numerator < denominator; numerator++) { if (gcd(numerator, denominator) == 1) { result.add(numerator + "/" + denominator); } } } return result; } // Helper function to compute Greatest Common Divisor using Euclidean algorithm private int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; }}Complexity
Time
O(n^2 * log(n)) - The two nested loops run in `O(n^2)` time. For each of the `O(n^2)` pairs, the GCD calculation using the Euclidean algorithm takes `O(log(min(numerator, denominator)))`, which is `O(log(n))` in the worst case.
Space
O(n^2) - The space is dominated by the storage required for the output list. The number of simplified fractions with denominator up to `n` is approximately `(3/π^2) * n^2`, which is `O(n^2)`.
Trade-offs
Pros
Simple to understand and implement.
Correctly identifies all simplified fractions.
Cons
Less efficient due to the repeated GCD calculations for O(n^2) pairs.
Solutions
Solution
class Solution { public List < String > simplifiedFractions ( int n ) { List < String > ans = new ArrayList <>(); for ( int i = 1 ; i < n ; ++ i ) { for ( int j = i + 1 ; j < n + 1 ; ++ j ) { if ( gcd ( i , j ) == 1 ) { ans . add ( i + "/" + j ); } } } return ans ; } private int gcd ( int a , int b ) { return b > 0 ? gcd ( b , a % b ) : a ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.