Skip to main content
Talentd

Simplified Fractions - Solution & Explanation

MediumMathStringNumber Theory9 min readAsked at: Google
Practice this problem

Problem Statement

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. You can return the answer in any order.

 

Example 1:

Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.

Example 2:

Input: n = 3
Output: ["1/2","1/3","2/3"]

Example 3:

Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".

 

Constraints:

  • 1 <= n <= 100

Approach Overview

Problem Overview: Given an integer n, return all fractions between 0 and 1 with denominators less than or equal to n that are already in their simplified form. A fraction a/b is valid only if 1 ≤ a < b ≤ n and gcd(a, b) = 1.

Approach 1: Brute Force with GCD Check (Time: O(n² log n), Space: O(1) excluding output)

Iterate over every possible denominator b from 2 to n. For each denominator, iterate the numerator a from 1 to b - 1. The fraction is simplified only when gcd(a, b) = 1. Use Euclid's algorithm to compute the GCD and append the string representation "a/b" to the result when the condition holds. The key insight: a fraction is already simplified exactly when numerator and denominator share no common divisor other than 1.

This approach directly models the definition of reduced fractions. You perform roughly n(n-1)/2 checks, and each GCD computation takes O(log n). The algorithm is simple, reliable, and works well within constraints. It relies on concepts from math and number theory.

Approach 2: Using Euler's Totient Function (Time: O(n log log n + n²), Space: O(n))

Euler's Totient Function φ(b) gives the number of integers in [1, b] that are coprime with b. For each denominator b, exactly φ(b) valid simplified fractions exist. You can precompute totients for all values up to n using a sieve-style method in O(n log log n) time.

Once the totient values are available, iterate through numerators and keep those that are coprime with the denominator. The totient insight helps reason about how many fractions should appear for each denominator and connects the problem to deeper number theory properties. This method is mostly educational here since we still enumerate candidate numerators, but the totient precomputation can be reused in other problems involving coprime counts.

Recommended for interviews: The brute force with GCD check is the expected solution. It shows you understand the mathematical definition of simplified fractions and can apply Euclid’s algorithm efficiently. Mentioning Euler’s Totient Function demonstrates stronger number theory knowledge, but interviewers typically look for the clean GCD-based enumeration.

Approach 1: Brute Force with GCD Check

This approach involves iterating over all possible denominators and numerators and checking if each pair is coprime using the gcd (greatest common divisor) function. If gcd(numerator, denominator) is 1, the fraction is simplified.

This solution uses two nested loops to iterate through every possible fraction with a denominator less than or equal to n. The gcd function is used to determine if the numerator and denominator are coprime.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n^2 * log(m)), where n is the input number and m is the larger number between the numerator and denominator, because calculating gcd takes O(log(m)).
Space Complexity: O(1) for storing results, not considering the output list.

Try this approach in the editor →

Approach 2: Using Euler's Totient Function

The fractions can also be generated using Euler's Totient Function, which calculates the number of integers up to a given integer that are coprime with it. This approach can be more efficient for certain applications but is complex to implement without specific libraries or integer properties handling in mind.

This solution uses Euler's Totient Function to precompute the number of integers that are coprime with each possible denominator. It maintains the previous gcd-check logic to generate simplified fractions.

Code

Python

Python

Complexity

Time Complexity: O(n * log(log n)) due to totient calculation + O(n^2) for iterating fractions.
Space Complexity: O(n) for storing the totient values.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force with GCD Check

Time Complexity: O(n^2 * log(m)), where n is the input number and m is the larger number between the numerator and denominator, because calculating gcd takes O(log(m)).
Space Complexity: O(1) for storing results, not considering the output list.

Using Euler's Totient Function

Time Complexity: O(n * log(log n)) due to totient calculation + O(n^2) for iterating fractions.
Space Complexity: O(n) for storing the totient values.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with GCD CheckO(n² log n)O(1)Standard solution for interviews. Directly checks if numerator and denominator are coprime.
Euler's Totient Function InsightO(n log log n + n²)O(n)Useful when studying number theory or when totient values are reused in multiple computations.

Video Solution

LeetCode 1447: Simplified Fractions • Knowledge Center • 2,623 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Simplified Fractions easy or hard?
Simplified Fractions is generally considered an easy-to-medium math problem. The implementation is straightforward once you recognize that a fraction is simplified when the numerator and denominator are coprime, which you can verify using the GCD algorithm.
Simplified Fractions Python/Java solution
In Python or Java, loop over denominators from 2 to n and numerators from 1 to denominator−1. Compute gcd(a, b); if it equals 1, append the formatted string "a/b" to the result list. Both languages provide efficient built-in or standard-library GCD implementations.
How to solve Simplified Fractions in O(n)?
Generating every simplified fraction cannot be done in strict O(n) time because the number of valid fractions itself grows roughly on the order of n². However, Euler’s Totient Function can compute how many simplified fractions exist for each denominator in O(n log log n) preprocessing time, though you still need enumeration to list them.
What is the best approach for Simplified Fractions?
The most practical approach iterates every numerator and denominator pair where 1 ≤ numerator < denominator ≤ n and keeps the fraction only when gcd(numerator, denominator) = 1. Euclid's algorithm makes the GCD check efficient, giving an overall time complexity of O(n² log n). This solution is simple and is the one typically expected in coding interviews.
Is Simplified Fractions asked at Google/Amazon/Meta?
Problems involving coprime numbers, GCD, and fraction reduction frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying concepts—Euclid’s algorithm and number theory reasoning—are commonly tested.
What data structure is used in Simplified Fractions?
No advanced data structure is required. The solution mainly uses nested iteration and the GCD function from number theory. Results are stored in a list of strings representing fractions such as "a/b".
What is the time complexity of Simplified Fractions?
The common solution runs in O(n² log n) time. There are about n²/2 numerator–denominator pairs to examine, and each pair requires a GCD computation that takes O(log n) using Euclid’s algorithm. Space complexity is O(1) excluding the output list of fractions.

Ready to solve this problem?

Practice Simplified Fractions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer