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 <= 100Problem 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.
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.
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.
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.
Python
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.
| Approach | Complexity |
|---|---|
| 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)). |
| Using Euler's Totient Function | Time Complexity: O(n * log(log n)) due to totient calculation + O(n^2) for iterating fractions. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with GCD Check | O(n² log n) | O(1) | Standard solution for interviews. Directly checks if numerator and denominator are coprime. |
| Euler's Totient Function Insight | O(n log log n + n²) | O(n) | Useful when studying number theory or when totient values are reused in multiple computations. |
LeetCode 1447: Simplified Fractions • Knowledge Center • 2,568 views views
Watch 9 more video solutions →Practice Simplified Fractions with our built-in code editor and test cases.
Practice on FleetCode