Abstract / Summary

List all fractions between zero and one with denominators up to a given number that cannot be simplified further

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (60k+ submissions).

Typical patterns to solve this problem:

• Math
• Number Theory
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method, simplifiedFractions. The method generates all proper fractions numerator/denominator for a given positive integer n such that the fraction is in its simplest form. It does so by iterating over every possible denominator from 1 through n and, for each denominator, iterating over every possible numerator that is strictly smaller than the denominator. A greatest-common-divisor (gcd) test discards any pair that is not coprime, and the remaining pairs are emitted as formatted strings.

Core Logic

Outer Denominator Loop

The outer loop establishes the range of denominators that will be examined.

for denominator in range(1, n + 1):

By starting at 1 and including n, the method guarantees coverage of the entire interval required by the problem statement. The loop variable denominator is used directly in the inner loop and later in the output string.

Inner Numerator Loop

For each selected denominator, the inner loop enumerates all numerators that produce a proper fraction (numerator < denominator).

for numerator in range(1, denominator):

The exclusive upper bound denominator ensures that the numerator never equals the denominator, thereby avoiding the generation of the value 1, which is not a proper fraction.

Coprime Check

The gcd test determines whether the current numerator and denominator share any common divisor greater than 1. Only pairs with a gcd of 1 are considered simplified.

if gcd(denominator, numerator) == 1:

The use of the built-in gcd function (available from the math module) provides a reliable and efficient way to perform this test.

Yielding the Result

When a coprime pair is found, the method yields a string representation of the fraction.

yield str(numerator) + "/" + str(denominator)

The concatenation builds the conventional “numerator/denominator” format expected by callers. Because the method uses yield, it returns a generator rather than a concrete list, enabling lazy evaluation.

Edge-Case Handling

When n is zero or one, the outer loop still executes but the inner loop’s range becomes empty (range(1, 1) or range(1, 0)), resulting in no yields. This behavior correctly produces an empty sequence, matching the definition that there are no proper fractions with denominators less than or equal to 1.

If n is negative, the range(1, n + 1) construct produces an empty range, again leading to no output. Although the problem domain typically restricts n to non-negative integers, the code gracefully handles out-of-range inputs without raising exceptions.

The gcd check inherently handles the case where either numerator or denominator is 1. Since gcd(1, x) always returns 1, every fraction with a numerator of 1 passes the coprime test, which is correct because such fractions are always in simplest form.

Performance Characteristics

The algorithm avoids constructing an intermediate collection of all candidate fractions. By employing a generator (yield), each fraction is produced on demand, which reduces memory consumption especially for large values of n.

The nested loops iterate exactly the number of integer pairs (numerator, denominator) where 1 ≤ numerator < denominator ≤ n. The gcd test filters out non-simplified fractions early, preventing unnecessary string construction for those pairs.

Using the standard library’s gcd function leverages an optimized Euclidean algorithm implementation, which is faster than a naïve divisor-counting approach. This choice contributes to overall efficiency, particularly when many denominator values are composite and have multiple common factors with potential numerators.

Because the method yields strings directly, there is no additional conversion step after the loops complete; the consumer of the generator receives each formatted fraction immediately. This design aligns well with streaming use cases where the full list of fractions is not required at once.

Overall, the combination of lazy generation, a tight coprime filter, and reliance on a highly optimized gcd routine results in a solution that scales gracefully with the input size while maintaining low runtime overhead.

Imagine you have a big box of colorful blocks and you want to make all the possible pairs of numbers that look like a fraction, which is just one number sitting on top of another one. The code starts by picking a bottom number for the fraction, and it counts up from one until it reaches the highest number allowed. Inside that, there is another loop that picks a top number for the fraction, but this number has to be smaller than the bottom one so the whole fraction stays smaller than one. Then, there is a special check that looks at both numbers to make sure they are friendly and do not share any common factors. If they are friendly, the computer puts them together with a little slash in the middle, like a tiny building block, and gives that fraction to you to see.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java			TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python			Java	Go	Rust	TS
	Progiez	C++	Python			Java
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai					Java
	fsq	C++
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007		Python
	lzl124631x	C++
	suxrobGM			C#
	trung-hn		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
suxrobGM	C#
trung-hn	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality