Domain 2MediumMEDIUM

Simplified Fractions

Generate simplified fractions between 0 and 1 with denominator <= n by iterating denominators, checking coprimality via GCD.

Domain: medium•Updated: 2026-09-16
#nested loops#list#O(n^2 log n)#output size

Problem Breakdown

We need to generate a list of unique strings representing fractions in their simplest form (irreducible). The constraints are:

  1. Range: Fractions must be strictly between 0 and 1 (0<fraction<10 < \text{fraction} < 1). This implies the numerator is always less than the denominator, and neither can be zero or negative within this context.
  2. Denominator Limit: The denominator dd cannot exceed n.
  3. Simplification: A fraction ab\frac{a}{b} is simplified if gcd(a,b)=1\text{gcd}(a, b) = 1. For example, “2/4” must be excluded because it simplifies to “1/2”.

Inputs: Integer n (1≤n≤1001 \le n \le 100). Outputs: A list of strings in the format "numerator/denominator". Implicit Constraints: No duplicates allowed. Order does not matter (per problem statement), but typically sorted by denominator then numerator is a natural side effect of our iteration order.

Intuition

A naive approach might be to generate all possible pairs (i,j)(i, j) where 1≤i<j≤n1 \le i < j \le n, convert them to strings, simplify each string mathematically (dividing both parts by their GCD), and then store the unique simplified results in a Set or List.

However, we can optimize this logic during generation:

  • Brute Force Complexity: If we generate all pairs without checking coprimality first, we end up with duplicates like “1/2” and “2/4”. We would need to simplify every single fraction before adding it to our result set. This involves a GCD calculation for every pair anyway (O(N2log⁡N)O(N^2 \log N)).
  • Key Insight: Instead of generating all pairs, simplifying them, then deduplicating, we can check the coprimality condition gcd(numerator,denominator)==1\text{gcd}(numerator, denominator) == 1 immediately. If they are coprime, this fraction is guaranteed to be unique and simplified relative to any other pair that could simplify down to it (e.g., if “2/4” exists in our iteration space, we skip it because gcd(2,4)=2 != 1).
  • Optimization: By filtering at the source using math.gcd, we avoid storing non-simplified forms and ensure uniqueness without needing a hash set for deduplication (though order doesn’t matter here).

Approach

  1. Initialize an empty list to store valid fraction strings.
  2. Iterate through every possible denominator dd from 2 up to n. We start at 2 because the smallest simplified proper fraction is “1/2”.
  3. For each denominator, iterate through numerators numnum starting from 1 up to d−1d-1. The numerator must be strictly less than the denominator for the value to remain between 0 and 1.
  4. Compute gcd(num,d)\text{gcd}(num, d). If it equals 1, append "num/dnum/d" to our list.
  5. Return the populated list.

Complexity Analysis

  • Time: We have two nested loops: one for denominators (2…n2 \dots n) and one for numerators (1…d−11 \dots d-1). This results in roughly n2/4n^2/4 iterations on average. Inside each iteration, we compute the GCD of two numbers up to size n. The Euclidean algorithm runs in O(log⁡(min⁡(num,den)))O(\log(\min(num, den))). Thus, total time complexity is O(n2⋅log⁡n)O(n^2 \cdot \log n). Given the constraint n≤100n \le 100, this is negligible.
  • Space: We store every valid simplified fraction found. The number of such fractions corresponds to the length of a Farey sequence at order n, which grows quadratically (≈3π2n2\approx \frac{3}{\pi^2} n^2). Therefore, space complexity for output storage is O(n2)O(n^2).

Solution

import math
from typing import List

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        res = []
        
        # Iterate through all valid denominators from 2 to n
        for d in range(2, n + 1):
            # Numerator must be less than denominator (exclusive of 0 and 1 boundaries)
            for num in range(1, d):
                # Check if the fraction is simplified by verifying GCD is 1
                if math.gcd(num, d) == 1:
                    res.append(f"{num}/{d}")
                    
        return res

## Edge Cases Handled
*   **n = 1:** The outer loop `range(2, 2)` does not execute. Returns an empty list `[]`, which is correct as no proper fractions exist with denominator $\le 1$.
*   **Duplicates (e.g., "2/4"):** By checking `math.gcd(num, d) == 1` before appending, we ensure that non-coprime pairs like $(2, 4)$ are skipped entirely. This prevents duplicates from entering the list naturally without requiring a separate deduplication step or Set lookup.
*   **Range Boundaries:** The loops strictly enforce $num \ge 1$ and $den > num$, ensuring no "0/5" (value 0) or "4/2" (value $\ge 1$) are included, satisfying the exclusive $(0, 1)$ constraint.