Problem Description

You need to find all simplified fractions between 0 and 1 (not including 0 or 1) where the denominator is at most n.

A simplified fraction means the numerator and denominator have no common factors other than 1 (they are coprime). For example, 2/4 is not simplified because both 2 and 4 share a common factor of 2, but 1/2 is simplified.

Given an integer n, return a list of strings representing all such fractions in the format "numerator/denominator". The fractions can be returned in any order.

For example, if n = 4, the valid simplified fractions between 0 and 1 would be:

• "1/2" (0.5)
• "1/3" (≈0.333)
• "2/3" (≈0.667)
• "1/4" (0.25)
• "3/4" (0.75)

Note that "2/4" is not included because it simplifies to "1/2" which is already in the list.

The solution uses a nested loop to check all possible numerator-denominator pairs where:

• The numerator i ranges from 1 to n-1
• The denominator j ranges from i+1 to n (ensuring the fraction is less than 1)
• Only pairs where gcd(i, j) == 1 are included (ensuring the fraction is simplified)

Intuition

To find all simplified fractions between 0 and 1, we need to think about what makes a fraction simplified and what constraints we have.

First, for a fraction to be between 0 and 1, the numerator must be smaller than the denominator. This gives us the relationship numerator < denominator.

Second, a fraction is in its simplest form when the numerator and denominator share no common factors except 1. This is equivalent to saying their greatest common divisor (GCD) equals 1. For instance, 2/6 and 1/3 represent the same value, but only 1/3 is simplified because gcd(1, 3) = 1, while gcd(2, 6) = 2.

Given these constraints, we can systematically generate all possible fractions by:

1. Trying every possible numerator from 1 to n-1 (we start from 1 because 0 would give us 0, which is excluded)
2. For each numerator, trying every possible denominator from numerator + 1 to n (ensuring the fraction is less than 1)
3. Checking if gcd(numerator, denominator) = 1 to ensure the fraction is already simplified

This approach naturally avoids duplicates. For example, when we check 2/4, we find gcd(2, 4) = 2, so we skip it. Later when we check 1/2, we find gcd(1, 2) = 1, so we include it. This way, each fraction value appears exactly once in its simplified form.

The key insight is that by checking the GCD condition, we automatically filter out all non-simplified fractions, leaving us with exactly the unique simplified fractions we need.

Learn more about Math patterns.

Solution Approach

The implementation uses a list comprehension with nested loops to generate all valid simplified fractions.

Here's how the solution works step by step:

1. Outer loop for numerators: We iterate i from 1 to n-1. Starting from 1 ensures we exclude 0 (which would give us 0/denominator = 0), and stopping at n-1 ensures we have room for denominators greater than the numerator.

2. Inner loop for denominators: For each numerator i, we iterate j from i+1 to n. Starting from i+1 guarantees that our fraction i/j will be less than 1 (since numerator < denominator). Going up to n respects the constraint that denominators should be at most n.

3. GCD check for simplification: We use gcd(i, j) == 1 to filter only simplified fractions. The gcd function (greatest common divisor) returns 1 only when the two numbers are coprime (share no common factors other than 1).

4. String formatting: Each valid fraction is formatted as f'{i}/{j}' using Python's f-string notation to create the required string representation.

The list comprehension elegantly combines all these steps:

[f'{i}/{j}' for i in range(1, n) for j in range(i + 1, n + 1) if gcd(i, j) == 1]

This approach has a time complexity of O(n² × log(n)) where:

• O(n²) comes from the nested loops
• O(log(n)) is the time complexity of computing GCD using Euclid's algorithm

The space complexity is O(k) where k is the number of simplified fractions generated, which depends on the value of n.

Example Walkthrough

Let's walk through the solution with n = 4 to see how we find all simplified fractions between 0 and 1.

Step 1: Set up our search space

• Numerators can range from 1 to 3 (i.e., 1 to n-1)
• For each numerator, denominators range from (numerator + 1) to 4

Step 2: Check each fraction

When i = 1 (numerator = 1):

• j = 2: Check 1/2 → gcd(1, 2) = 1 ✓ Add "1/2"
• j = 3: Check 1/3 → gcd(1, 3) = 1 ✓ Add "1/3"
• j = 4: Check 1/4 → gcd(1, 4) = 1 ✓ Add "1/4"

When i = 2 (numerator = 2):

• j = 3: Check 2/3 → gcd(2, 3) = 1 ✓ Add "2/3"
• j = 4: Check 2/4 → gcd(2, 4) = 2 ✗ Skip (not simplified)

When i = 3 (numerator = 3):

• j = 4: Check 3/4 → gcd(3, 4) = 1 ✓ Add "3/4"

Step 3: Collect results Final list: ["1/2", "1/3", "1/4", "2/3", "3/4"]

Notice how 2/4 was automatically excluded because gcd(2, 4) = 2, preventing the duplicate representation of 1/2. This demonstrates how the GCD check ensures each fraction appears exactly once in its simplified form.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × log(min(i, j)))

The code uses nested loops where:

• The outer loop runs from i = 1 to i = n-1, which is O(n) iterations
• The inner loop runs from j = i+1 to j = n, which averages to O(n) iterations
• For each pair (i, j), we compute gcd(i, j) which takes O(log(min(i, j))) time using the Euclidean algorithm

The total number of pairs checked is approximately n²/2, and for each pair we perform a GCD operation. Therefore, the overall time complexity is O(n² × log(n)), which can be simplified to O(n² × log(min(i, j))) for precision.

Space Complexity: O(φ(2) + φ(3) + ... + φ(n)) ≈ O(n²)

The space is used to store the result list. The number of simplified fractions with denominator d equals φ(d) (Euler's totient function), where φ(d) counts integers less than d that are coprime to d.

The total number of simplified fractions is the sum of totient values from 2 to n: Σφ(k) for k = 2 to n. This sum is approximately 3n²/π² for large n, which gives us O(n²) space complexity.

Additionally, the list comprehension itself doesn't use extra space beyond the output list, making the overall space complexity O(n²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Range Boundaries Leading to Missing or Invalid Fractions

One of the most common mistakes is getting the loop ranges wrong, which can result in:

• Including fractions equal to or greater than 1
• Missing valid fractions
• Including 0 as a fraction

Incorrect Implementation Example:

# Pitfall 1: Starting denominator from i instead of i+1
for numerator in range(1, n):
    for denominator in range(numerator, n + 1):  # Wrong! Includes i/i = 1
        if gcd(numerator, denominator) == 1:
            result.append(f'{numerator}/{denominator}')

# Pitfall 2: Incorrect upper bound for numerator
for numerator in range(1, n + 1):  # Wrong! When numerator = n, no valid denominators exist
    for denominator in range(numerator + 1, n + 1):
        # When numerator = n, this loop never executes since n+1 > n+1

Solution: Ensure the ranges are:

• Numerator: range(1, n) - starts at 1 (excludes 0) and goes up to n-1
• Denominator: range(numerator + 1, n + 1) - ensures fraction < 1 and includes n as possible denominator

2. Forgetting to Import GCD or Using Wrong GCD Implementation

Incorrect Implementation Example:

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        # Forgot to import gcd!
        return [f'{i}/{j}' for i in range(1, n) 
                for j in range(i + 1, n + 1) 
                if gcd(i, j) == 1]  # NameError: name 'gcd' is not defined

Solution: Always import gcd from the math module:

from math import gcd

Alternatively, implement your own GCD function:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

3. Not Understanding What "Simplified" Means

Some might think checking numerator < denominator is enough, forgetting about the coprime requirement.

Incorrect Implementation Example:

# Wrong: This includes non-simplified fractions like "2/4"
return [f'{i}/{j}' for i in range(1, n) 
        for j in range(i + 1, n + 1)]  # Missing GCD check!

Solution: Always check that gcd(numerator, denominator) == 1 to ensure the fraction cannot be reduced further.

4. Performance Issues with Large Values of n

While the given solution is efficient, some might try alternative approaches that are less optimal:

Inefficient Approach Example:

# Generating all fractions first, then removing duplicates
fractions = set()
for denominator in range(2, n + 1):
    for numerator in range(1, denominator):
        # Simplify the fraction first
        g = gcd(numerator, denominator)
        simplified_num = numerator // g
        simplified_den = denominator // g
        fractions.add(f'{simplified_num}/{simplified_den}')
return list(fractions)

This approach has unnecessary overhead from:

• Creating simplified versions of non-simplified fractions
• Using a set for deduplication
• Extra division operations

Solution: Stick with the direct approach of only generating simplified fractions by checking gcd(i, j) == 1 before adding to the result.