Problem Statement

Given an integer n, return all simplified fractions between 0 and 1 (exclusive) such that the denominator is less than or equal to n. A simplified fraction is a fraction where the numerator and denominator are coprime (i.e., their greatest common divisor is 1).

Example 1:
Input: n = 2
Output: ["1/2"]

Example 2:
Input: n = 3
Output: ["1/2","1/3","2/3"]

Constraints:

• 1 <= n <= 100

---

Approach in Plain English

1. We need all fractions numerator/denominator where:
   • numerator < denominator (so fraction < 1)
   • denominator <= n
2. A fraction is simplified if the numerator and denominator are coprime (their greatest common divisor (GCD) is 1).
3. So, for each denominator from 2 to n:
   • Loop over numerators from 1 to denominator-1.
   • Check if GCD(numerator, denominator) == 1. If yes, include the fraction.
4. Use Euclidean algorithm to calculate GCD efficiently.
5. Collect all valid fractions in a list and return.

Key idea: Only add fractions where numerator and denominator share no common factor besides 1.

---

Dry Run Example

Let’s take n = 4.

1. Initialize an empty list res = [].
2. Loop over denominator from 2 to 4.
   • denominator = 2:
     • numerator = 1 → GCD(1, 2) = 1 → add “1/2” → res = ["1/2"]
   • denominator = 3:
     • numerator = 1 → GCD(1, 3) = 1 → add “1/3” → res = ["1/2","1/3"]
     • numerator = 2 → GCD(2, 3) = 1 → add “2/3” → res = ["1/2","1/3","2/3"]
   • denominator = 4:
     • numerator = 1 → GCD(1, 4) = 1 → add “1/4” → res = ["1/2","1/3","2/3","1/4"]
     • numerator = 2 → GCD(2, 4) = 2 → skip (not simplified)
     • numerator = 3 → GCD(3, 4) = 1 → add “3/4” → res = ["1/2","1/3","2/3","1/4","3/4"]
3. Return res.

---

Textual Approach

• Loop over possible denominators.
• Loop over numerators less than denominator.
• Use Euclidean GCD check to filter fractions.
• Add valid simplified fractions to the result list.

---

Java Code

import java.util.ArrayList;
import java.util.List;

public class SimplifiedFractions {
    
    public static List<String> simplifiedFractions(int n) {
        List<String> res = new ArrayList<>();
        
        for (int denominator = 2; denominator <= n; denominator++) {
            for (int numerator = 1; numerator < denominator; numerator++) {
                if (gcd(numerator, denominator) == 1) { // simplified fraction
                    res.add(numerator + "/" + denominator);
                }
            }
        }
        
        return res;
    }
    
    // Euclidean algorithm to calculate GCD
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        int n = 4;
        List<String> fractions = simplifiedFractions(n);
        System.out.println(fractions); // Output: [1/2, 1/3, 2/3, 1/4, 3/4]
    }
}

---

Key Points

• The GCD function is crucial to check if a fraction is simplified.
• Time Complexity:
  O(n² log(max(numerator, denominator))) — because for each denominator we loop through numerators and compute GCD.
• Space Complexity: O(number of simplified fractions), for storing the result.