Watch 10 video solutions for Simplified Fractions, a medium level problem involving Math, String, Number Theory. This walkthrough by Knowledge Center has 2,568 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |