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 <= 100The goal of #1447 Simplified Fractions is to generate all fractions between 0 and 1 whose denominators are less than or equal to n, while ensuring each fraction is already in its reduced (simplified) form. A common way to think about this is to iterate through all possible denominators and pair them with numerators smaller than the denominator.
For each candidate fraction numerator/denominator, we must ensure it is in its simplest form. This can be checked by computing the greatest common divisor (GCD) of the numerator and denominator. If gcd(numerator, denominator) == 1, the fraction is already simplified and can be added to the result list as a string.
This approach systematically explores all valid numerator–denominator pairs while filtering out reducible fractions. Efficient GCD computation keeps the process fast. The method mainly involves nested iteration and number theory concepts, with time complexity around O(n² log n) due to repeated GCD calculations and linear space for storing the resulting fractions.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Enumerate numerator and denominator pairs with GCD check | O(n² log n) | O(k) for storing valid fractions |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
A fraction is fully simplified if there is no integer that divides cleanly into the numerator and denominator.
In other words the greatest common divisor of the numerator and the denominator of a simplified fraction is 1.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in coding interviews to test understanding of number theory concepts like GCD, iteration patterns, and basic mathematical reasoning. It is commonly seen in medium-level interview practice sets.
The optimal approach iterates through all denominators from 2 to n and numerators less than each denominator. For every pair, compute the GCD and include the fraction only if the GCD equals 1. This ensures the fraction is already in its simplest form.
The GCD helps determine whether a fraction can be reduced further. If the greatest common divisor of the numerator and denominator is 1, the fraction is already simplified and should be included in the result.
A dynamic list or array of strings is typically used to store the valid fractions. Each simplified fraction is formatted as a string like "a/b" before being added to the list.