Solution Explanation for Simplified Fractions

This problem asks to generate a list of all simplified fractions between 0 and 1 (exclusive) where the denominator is less than or equal to a given integer n. A simplified fraction is one where the numerator and denominator have no common divisors other than 1 (their greatest common divisor, or GCD, is 1).

Approach

The most straightforward approach is to iterate through all possible numerator and denominator pairs and check if their GCD is 1.

1. Nested Loops: We use nested loops to iterate through all possible pairs (i, j) where 1 <= i < j <= n. i represents the numerator and j represents the denominator. The condition i < j ensures that the fraction is less than 1.

2. GCD Calculation: For each pair (i, j), we compute their greatest common divisor (GCD) using Euclid's algorithm. This algorithm efficiently finds the GCD of two numbers.

3. Simplified Fraction Check: If the GCD of i and j is 1, it means the fraction is simplified, and we add it to the result list as a string (e.g., "1/2").

4. Return: Finally, we return the list of simplified fractions.

Time and Space Complexity Analysis

• Time Complexity: The nested loops iterate approximately n(n-1)/2 times (sum of integers from 1 to n-1). The GCD calculation takes O(log(min(i, j))) time in each iteration. Therefore, the overall time complexity is approximately O(n² log n) but can be considered O(n²) in practice since the log n term is relatively small.

• Space Complexity: The space complexity is dominated by the size of the result list. In the worst-case scenario (when most fractions are simplified), the list can contain O(n²) elements. Therefore, the space complexity is O(n²).

Code Implementation with Euclid's Algorithm (GCD)

The code examples provided in various languages use Euclid's algorithm to compute the GCD. Euclid's algorithm is a highly efficient method for finding the greatest common divisor of two integers. It's based on the principle that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. This process is repeated until one of the numbers becomes 0; the other number is the GCD. A recursive implementation is shown below:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

Other languages use similar recursive or iterative implementations of Euclid's algorithm. The core idea remains the same: repeatedly apply the modulo operation until the remainder is 0.

Example in Python

def simplifiedFractions(n: int) -> List[str]:
    result = []
    for i in range(1, n):
        for j in range(i + 1, n + 1):
            if gcd(i, j) == 1:
                result.append(str(i) + "/" + str(j))
    return result
 
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
 

This Python code directly implements the described approach, using nested loops and the GCD function. Other language implementations follow a similar structure, adapting the syntax and function calls accordingly.