LeetCode 1447 - Simplified Fractions

LeetCode Problem 1447

Difficulty: 🟡 Medium
Topics: Math, String, Number Theory

Solution

Problem Understanding

The problem asks us to generate all simplified fractions between 0 and 1 (exclusive) where the denominator does not exceed a given integer n. A simplified fraction is one in which the numerator and denominator are coprime, meaning their greatest common divisor (GCD) is 1. For example, 2/4 is not simplified because it reduces to 1/2. The input is a single integer n, representing the maximum denominator allowed, and the output is a list of strings representing all valid simplified fractions. The order of fractions in the output does not matter.

Constraints are 1 <= n <= 100, which indicates that the input size is small, so a direct approach iterating over all possible numerator-denominator pairs is feasible. Important edge cases include n = 1, where there are no fractions between 0 and 1, and n = 2, which is the smallest case that produces a valid fraction (1/2).

Approaches

The brute-force approach is straightforward: iterate over all pairs of integers (numerator, denominator) where 1 <= numerator < denominator <= n and check if the numerator and denominator are coprime by computing their GCD. If they are coprime, include the fraction in the result. This approach guarantees correctness because it checks every possible fraction that could be simplified.

The key insight for an optimal solution is that checking GCD for every pair is already efficient for n <= 100, but we can slightly improve by generating fractions only for numerators less than the denominator, avoiding unnecessary iterations. Beyond that, the problem is small enough that brute-force with GCD checks is effectively optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2 * log(max(numerator, denominator)))	O(n^2)	Iterate all numerator-denominator pairs and check coprime via GCD
Optimal	O(n^2 * log n)	O(n^2)	Same as brute force; optimized by skipping numerator >= denominator

Algorithm Walkthrough

1. Initialize an empty list result to store simplified fraction strings.
2. Loop over each denominator from 2 to n inclusive. Start from 2 because fractions with denominator 1 are not between 0 and 1.
3. For each denominator, loop over numerator from 1 to denominator - 1. This ensures all fractions are strictly less than 1.
4. For each (numerator, denominator) pair, calculate the GCD of numerator and denominator.
5. If the GCD equals 1, the fraction is simplified. Convert it to a string in the format "numerator/denominator" and append it to result.
6. After all loops finish, return result.

Why it works: By iterating over all possible numerator-denominator pairs where the numerator is smaller than the denominator and filtering out non-coprime pairs, we ensure that all fractions are unique, simplified, and strictly between 0 and 1. The GCD check guarantees no fraction can be reduced further.

Python Solution

from typing import List
from math import gcd

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        result = []
        for denominator in range(2, n + 1):
            for numerator in range(1, denominator):
                if gcd(numerator, denominator) == 1:
                    result.append(f"{numerator}/{denominator}")
        return result

The Python implementation follows the algorithm exactly. We import gcd from the math module for coprimality checks. The outer loop iterates over denominators starting from 2, and the inner loop iterates over numerators less than the denominator. Only fractions with GCD 1 are included in the final result as strings.

Go Solution

package main

import (
    "fmt"
    "strconv"
)

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func simplifiedFractions(n int) []string {
    result := []string{}
    for denominator := 2; denominator <= n; denominator++ {
        for numerator := 1; numerator < denominator; numerator++ {
            if gcd(numerator, denominator) == 1 {
                fraction := strconv.Itoa(numerator) + "/" + strconv.Itoa(denominator)
                result = append(result, fraction)
            }
        }
    }
    return result
}

In Go, we manually implement the GCD function using Euclid's algorithm. We build the result as a slice of strings. The loop logic mirrors the Python version. String conversion is done using strconv.Itoa, and slices dynamically grow as fractions are added.

Worked Examples

Example 1: n = 2

Denominator	Numerator	GCD	Include?	Result
2	1	1	Yes	["1/2"]

Example 2: n = 3

Denominator	Numerator	GCD	Include?	Result
2	1	1	Yes	["1/2"]
3	1	1	Yes	["1/2","1/3"]
3	2	1	Yes	["1/2","1/3","2/3"]

Example 3: n = 4

Denominator	Numerator	GCD	Include?	Result
2	1	1	Yes	["1/2"]
3	1	1	Yes	["1/2","1/3"]
3	2	1	Yes	["1/2","1/3","2/3"]
4	1	1	Yes	["1/2","1/3","2/3","1/4"]
4	2	2	No	["1/2","1/3","2/3","1/4"]
4	3	1	Yes	["1/2","1/3","2/3","1/4","3/4"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2 * log n)	There are O(n^2) numerator-denominator pairs, and GCD computation takes O(log n)
Space	O(n^2)	At most O(n^2) simplified fractions can exist, stored in the result list

The complexity is dominated by iterating over numerator-denominator pairs and performing GCD checks. The space requirement is proportional to the number of valid fractions.

Test Cases

# Provided examples
assert Solution().simplifiedFractions(2) == ["1/2"]  # smallest valid fraction
assert set(Solution().simplifiedFractions(3)) == set(["1/2","1/3","2/3"])  # multiple fractions
assert set(Solution().simplifiedFractions(4)) == set(["1/2","1/3","1/4","2/3","3/4"])  # skip non-simplified

# Boundary tests
assert Solution().simplifiedFractions(1) == []  # no fractions possible
assert set(Solution().simplifiedFractions(5)) == set(["1/2","1/3","2/3","1/4","3/4","1/5","2/5","3/5","4/5"])  # larger n

# Stress test
assert len(Solution().simplifiedFractions(100)) > 0  # large n, non-empty result

Test	Why
n = 2	Minimal case producing a fraction
n = 3	Small multiple fractions
n = 4	Avoids non-simplified fraction inclusion
n = 1	Edge case with no valid fraction
n = 5	Slightly larger n to verify correctness
n = 100	Stress test for algorithm performance

Edge Cases

Edge Case 1: n = 1

No fractions exist between 0 and 1 with denominator ≤ 1. Implementation correctly returns an empty list by starting the denominator loop at 2.

Edge Case 2: Fractions reducible to smaller fractions

Fractions like 2/4 must be excluded. The GCD check guarantees that only coprime numerator-denominator pairs are included.

Edge Case 3: Large n approaching constraint limit

For n = 100, there are many numerator-denominator pairs. The algorithm handles this efficiently using simple loops and GCD checks, and the result list dynamically grows to accommodate all simplified fractions without exceeding memory limits.