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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Simplified Fractions

Number: 1543

Difficulty: Medium

Paid? No

Companies: Google

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. A fraction is considered simplified if the greatest common divisor (GCD) of its numerator and denominator is 1.

Key Insights

  • Only consider denominators from 2 to n since fractions with denominator 1 (like 1/1) are not between 0 and 1.
  • For each denominator, iterate over possible numerators from 1 up to denominator - 1.
  • Use the GCD of numerator and denominator to check if the fraction is in simplified form.
  • The overall time complexity is driven by the nested loop over denominators and numerators.

Space and Time Complexity

Time Complexity: O(n^2 * log(n)) – Iterating through all possible pairs (numerator, denominator) and performing a GCD computation which takes logarithmic time. Space Complexity: O(n^2) – In the worst case, storing up to O(n^2) fraction strings.

Solution

We iterate through all denominators d from 2 to n, and for each d, we iterate through all numerators from 1 to d - 1. For every fraction numerator/d, we check if the GCD of numerator and denominator is 1. If yes, then the fraction is simplified and we add it to our result list as a string "numerator/denom".
The algorithm primarily uses loops and a helper function (or method) for computing the GCD. The main gotcha is correctly checking that a fraction is in its simplest form by ensuring that the numerator and denominator are co-prime.

Code Solutions

import math  # Import math module to use the gcd function

def simplifiedFractions(n):
    result = []  # Initialize list to store the simplified fractions
    # Iterate over each denominator from 2 to n
    for denom in range(2, n + 1):
        # Iterate over possible numerators from 1 up to denom-1
        for num in range(1, denom):
            # Check if the fraction num/denom is simplified by comparing gcd with 1
            if math.gcd(num, denom) == 1:
                # If simplified, add the fraction string to the result list
                result.append(f"{num}/{denom}")
    return result

# Example usage:
print(simplifiedFractions(4))  # Expected output: ["1/2", "1/3", "1/4", "2/3", "3/4"]
← Back to All Questions