# Simplified Fractions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/simplified-fractions)
Canonical: https://scaleengineer.com/dsa/problems/simplified-fractions
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** String
---
## Problem
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
## Brute Force with GCD Check
This approach iterates through all possible numerators and denominators and checks if they form a simplified fraction by calculating their Greatest Common Divisor (GCD).
**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)`.
**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.
### Explanation
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.
```java
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;
    }
}
```
### Algorithm
- 1. Initialize an empty list `result` to store the fraction strings.
- 2. Iterate through all possible denominators `d` from `2` to `n`.
- 3. For each `d`, iterate through all possible numerators `num` from `1` to `d-1`.
- 4. Calculate the greatest common divisor (GCD) of `num` and `d` using a helper function (e.g., Euclidean algorithm).
- 5. If `gcd(num, d) == 1`, the fraction is simplified. Add the string `num + "/" + d` to the `result` list.
- 6. After all loops complete, return the `result` list.

## Generating Fractions using Farey Sequences (Mediant Method)
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.
**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.
**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.
### Explanation
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.
```java
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;
        }
        generate(0, 1, 1, 1, n, result);
        return result;
    }

    private void generate(int num1, int den1, int num2, int den2, int n, List<String> result) {
        int mediantNum = num1 + num2;
        int mediantDen = den1 + den2;

        if (mediantDen > n) {
            return;
        }

        result.add(mediantNum + "/" + mediantDen);
        generate(num1, den1, mediantNum, mediantDen, n, result);
        generate(mediantNum, mediantDen, num2, den2, n, result);
    }
}
```
### Algorithm
- 1. Initialize an empty list `result`.
- 2. Define a recursive function `generate(num1, den1, num2, den2, n, result)` that finds fractions between `num1/den1` and `num2/den2`.
- 3. Start the process by calling `generate(0, 1, 1, 1, n, result)` to find all fractions between 0 and 1.
- 4. 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)`.
- 5. Return the `result` list.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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 ]
```