We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Simplified Fractions

Difficulty: Medium

Problem Description

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.

Key Insights

  • A fraction is simplified if the greatest common divisor (GCD) of the numerator and denominator is 1.
  • The numerator must be less than the denominator to ensure the fraction is between 0 and 1.
  • For each denominator from 2 to n, we can generate numerators from 1 to (denominator - 1) and check if they form a simplified fraction.

Space and Time Complexity

Time Complexity: O(n^2 * log(k)), where n is the input integer and k is the average size of the numbers being checked for GCD. Space Complexity: O(n), for storing the resulting list of fractions.

Solution

To solve the problem, we iterate through all possible denominators from 2 to n. For each denominator, we iterate through possible numerators from 1 to (denominator - 1). We check if the GCD of the numerator and denominator is 1 to determine if it is a simplified fraction. If it is, we store the fraction as a string in the format "numerator/denominator".

Code Solutions

from math import gcd

def simplifiedFractions(n):
    result = []
    for denominator in range(2, n + 1):
        for numerator in range(1, denominator):
            if gcd(numerator, denominator) == 1:
                result.append(f"{numerator}/{denominator}")
    return result
← Back to All Questions