Simplified Fractions

Med

#1337Time: 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)`.

Patterns

Math Number Theory

Data structures

String

Prompt

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

1. Initialize an empty list result to store the fraction strings.
1. Iterate through all possible denominators d from 2 to n.
1. For each d, iterate through all possible numerators num from 1 to d-1.
1. Calculate the greatest common divisor (GCD) of num and d using a helper function (e.g., Euclidean algorithm).
1. If gcd(num, d) == 1, the fraction is simplified. Add the string num + "/" + d to the result list.
1. After all loops complete, return the result list.

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<String> simplifiedFractions(int n) {6        List<String> result = new ArrayList<>();7        if (n < 2) {8            return result;9        }10        for (int denominator = 2; denominator <= n; denominator++) {11            for (int numerator = 1; numerator < denominator; numerator++) {12                if (gcd(numerator, denominator) == 1) {13                    result.add(numerator + "/" + denominator);14                }15            }16        }17        return result;18    }19 20    // Helper function to compute Greatest Common Divisor using Euclidean algorithm21    private int gcd(int a, int b) {22        while (b != 0) {23            int temp = b;24            b = a % b;25            a = temp;26        }27        return a;28    }29}

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.

This approach leverages properties of Farey sequences and mediants to generate only the simplified fractions directly, avoiding the need for GCD checks, making it more efficient.

Algorithm

1. Initialize an empty list result.
1. Define a recursive function generate(num1, den1, num2, den2, n, result) that finds fractions between num1/den1 and num2/den2.
1. Start the process by calling generate(0, 1, 1, 1, n, result) to find all fractions between 0 and 1.
1. Inside generate:
- a. Calculate the mediant fraction m = (num1+num2)/(den1+den2).
- b. If the denominator of m is greater than n, return (base case).
- c. Add the string representation of m to the result list.
- d. Recursively call generate for the left interval: generate(num1, den1, m.num, m.den, n, result).
- e. Recursively call generate for the right interval: generate(m.num, m.den, num2, den2, n, result).
1. Return the result list.

Walkthrough

This method is based on the properties of the Stern-Brocot tree or Farey sequences. All positive simplified fractions can be generated starting from 0/1 and 1/1 and recursively finding their "mediant". The mediant of two fractions a/b and c/d is (a+c)/(b+d). A key property is that if a/b and c/d are simplified, their mediant is also a simplified fraction that lies between them. We can use a recursive approach. We start with the interval (0/1, 1/1). In each step, we take two fractions f1 = a/b and f2 = c/d and calculate their mediant m = (a+c)/(b+d). If the denominator of m is less than or equal to n, it's a valid fraction. We add it to our result list and then recursively explore the two new sub-intervals: (f1, m) and (m, f2). The recursion stops when the mediant's denominator exceeds n. This method cleverly avoids generating non-simplified fractions and thus doesn't need any GCD checks.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<String> simplifiedFractions(int n) {6        List<String> result = new ArrayList<>();7        if (n < 2) {8            return result;9        }10        generate(0, 1, 1, 1, n, result);11        return result;12    }13 14    private void generate(int num1, int den1, int num2, int den2, int n, List<String> result) {15        int mediantNum = num1 + num2;16        int mediantDen = den1 + den2;17 18        if (mediantDen > n) {19            return;20        }21 22        result.add(mediantNum + "/" + mediantDen);23        generate(num1, den1, mediantNum, mediantDen, n, result);24        generate(mediantNum, mediantDen, num2, den2, n, result);25    }26}

Complexity

Time

O(n^2) - The number of recursive calls is equal to the number of simplified fractions generated, which is `O(n^2)`. Each call performs constant time operations. This is faster than the brute-force approach as it eliminates the `O(log n)` factor from the GCD calculation.

Space

O(n^2) - The space for the result list is `O(n^2)`. The recursion depth can go up to `O(n)`, so the call stack uses `O(n)` space. The total space is dominated by the result list.

Trade-offs

Pros

More efficient as it avoids explicit GCD calculations.
Directly generates only the required simplified fractions.

Cons

The concept of mediants and Farey sequences might be less intuitive than the direct brute-force approach.
A recursive implementation can lead to a stack overflow for very large n, though n <= 100 is safe. An iterative version using a stack can avoid this.

Solutions

Solution

1class 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 ; } }

1class Solution { public: vector < string > simplifiedFractions ( int n ) { vector < string > ans ; for ( int i = 1 ; i < n ; ++ i ) { for ( int j = i + 1 ; j < n + 1 ; ++ j ) { if ( __gcd ( i , j ) == 1 ) { ans . push_back ( to_string ( i ) + "/" + to_string ( j )); } } } return ans ; } };

1class Solution : def simplifiedFractions ( self , n : int ) -> List [ str ]: return [ f ' { i } / { j } ' for i in range ( 1 , n ) for j in range ( i + 1 , n + 1 ) if gcd ( i , j ) == 1 ]

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.

← Previous

Previous problem

Next problem