Problem Description

The Simplified Fractions problem asks you to generate a list of all simplified fractions between 0 and 1 (exclusive) where the denominators are less than or equal to a given integer n. A fraction is considered simplified if the numerator and denominator are coprime (i.e., their greatest common divisor is 1).

Given an integer n, return a list of strings representing all simplified fractions with denominators from 2 up to n (inclusive) and numerators from 1 up to one less than the denominator.

Constraints:

• 1 <= n <= 100
• Each valid fraction is in the form "numerator/denominator".
• Each fraction must be in its lowest terms (simplified form).
• Do not include duplicate fractions.
• Fractions must be less than 1 (i.e., numerator < denominator).

Thought Process

To solve this problem, the first idea is to generate all possible fractions where the numerator is less than the denominator, and the denominator is between 2 and n. For each possible pair, we need to check if the fraction is already simplified.

The brute-force way is to loop through every possible numerator and denominator, and for each, check if their greatest common divisor (GCD) is 1. If it is, the fraction is in its lowest terms and should be included.

The optimization comes from the realization that checking for simplification can be done efficiently using the Euclidean algorithm to compute GCD. There's no need to store or compare previously seen fractions, because the GCD check ensures uniqueness and lowest terms automatically.

This approach is direct and leverages number theory (coprimality) for correctness and efficiency.

Solution Approach

Let's break down the algorithm step by step:

1. Iterate through denominators:
   • Loop through all possible denominators d from 2 to n (inclusive).
2. Iterate through numerators:
   • For each denominator d, loop through all numerators num from 1 to d-1.
3. Check for coprimality:
   • For each pair (num, d), calculate the greatest common divisor (GCD).
   • If gcd(num, d) == 1, the fraction is simplified.
4. Store the result:
   • If the fraction is simplified, add the string "num/d" to the result list.
5. Return the result:
   • After all iterations, return the list of simplified fraction strings.

We use the Euclidean algorithm to efficiently compute the GCD, which is available as a standard library function in most languages.

Example Walkthrough

Let's walk through the process with n = 4:

• Denominator = 2:
  • Numerator = 1: gcd(1,2) = 1 → "1/2"
• Denominator = 3:
  • Numerator = 1: gcd(1,3) = 1 → "1/3"
  • Numerator = 2: gcd(2,3) = 1 → "2/3"
• Denominator = 4:
  • Numerator = 1: gcd(1,4) = 1 → "1/4"
  • Numerator = 2: gcd(2,4) = 2 → skip
  • Numerator = 3: gcd(3,4) = 1 → "3/4"

The final output is: ["1/2", "1/3", "2/3", "1/4", "3/4"]

Time and Space Complexity

Brute-force approach:

• We check all numerators and denominators, giving O(n²) pairs.
• For each pair, we check for simplification by reducing the fraction, which can be costly if done by repeated subtraction or division.

• Still O(n²) pairs, but GCD computation is O(log d) per pair.
• Total time complexity: O(n² log n)
• Space complexity: O(n²) in the worst case, but in practice much less since only coprime pairs are stored.

The use of the Euclidean algorithm makes the GCD check efficient, so the solution is fast enough for the given constraints.

Code Implementation

from math import gcd

class Solution:
    def simplifiedFractions(self, n: int):
        res = []
        for d in range(2, n+1):
            for num in range(1, d):
                if gcd(num, d) == 1:
                    res.append(f"{num}/{d}")
        return res
      

#include <vector>
#include <string>
#include <numeric>
using namespace std;

class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> res;
        for (int d = 2; d <= n; ++d) {
            for (int num = 1; num < d; ++num) {
                if (gcd(num, d) == 1) {
                    res.push_back(to_string(num) + "/" + to_string(d));
                }
            }
        }
        return res;
    }
};
      

import java.util.*;
class Solution {
    public List<String> simplifiedFractions(int n) {
        List<String> res = new ArrayList<>();
        for (int d = 2; d <= n; d++) {
            for (int num = 1; num < d; num++) {
                if (gcd(num, d) == 1) {
                    res.add(num + "/" + d);
                }
            }
        }
        return res;
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }
}
      

var simplifiedFractions = function(n) {
    const res = [];
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    for (let d = 2; d <= n; d++) {
        for (let num = 1; num < d; num++) {
            if (gcd(num, d) === 1) {
                res.push(num + "/" + d);
            }
        }
    }
    return res;
};
      

Summary

The Simplified Fractions problem is a classic exercise in number theory and iteration. By leveraging the GCD function, we efficiently filter out only those fractions that are already in their simplest form. The approach is both intuitive and optimal for the problem constraints, making it a great example of how mathematical insight can simplify code and improve performance.