Problem Breakdown
We need to generate a list of unique strings representing fractions in their simplest form (irreducible). The constraints are:
- Range: Fractions must be strictly between 0 and 1 (). This implies the numerator is always less than the denominator, and neither can be zero or negative within this context.
- Denominator Limit: The denominator cannot exceed
n. - Simplification: A fraction is simplified if . For example, “2/4” must be excluded because it simplifies to “1/2”.
Inputs: Integer n ().
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 where , 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 ().
- Key Insight: Instead of generating all pairs, simplifying them, then deduplicating, we can check the coprimality condition 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
- Initialize an empty list to store valid fraction strings.
- Iterate through every possible denominator from 2 up to
n. We start at 2 because the smallest simplified proper fraction is “1/2”. - For each denominator, iterate through numerators starting from 1 up to . The numerator must be strictly less than the denominator for the value to remain between 0 and 1.
- Compute . If it equals 1, append "" to our list.
- Return the populated list.
Complexity Analysis
- Time: We have two nested loops: one for denominators () and one for numerators (). This results in roughly iterations on average. Inside each iteration, we compute the GCD of two numbers up to size
n. The Euclidean algorithm runs in . Thus, total time complexity is . Given the constraint , 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 (). Therefore, space complexity for output storage is .
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.