Simplified Fractions - Leetcode Solution

Problem Statement:

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. The fractions can be in any order.

Example:

Input: n = 3 Output: ["1/2","1/3","2/3"] Explanation: There are three fractions between 0 and 1 with a denominator less-than-or-equal-to 3: 1/2, 1/3, and 2/3.

Solution:

To solve this problem, we can use 2 loops i and j, where i represents the numerator and j represents the denominator.

• We start the loop from i=1 to i<n and inside that loop, j starts from i+1 to j<=n. This is because we don't want to calculate the same fractions multiple times, we only calculate the fraction where numerator < denominator.
• We check if the greatest common divisor (GCD) between the numerator and denominator is 1, if it is not 1, then the fraction is not simplified, so skip it.
• If the GCD is 1, add the fraction to the result list as a string in the format "numerator/denominator".
• Return the result list.

The GCD of two numbers can be calculated using the Euclidean algorithm. We use the following formula to calculate the GCD:

gcd(a,b) = gcd(b,a%b) for a > b gcd(a,a) = a

The Python code for the solution is given below:

class Solution: def simplifiedFractions(self, n: int) -> List[str]: res = [] for i in range(1, n): for j in range(i+1, n+1): if self.gcd(i, j) == 1: res.append(str(i) + '/' + str(j)) return res

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

Time Complexity:

The time complexity of this solution is O(n^2 log n) because we are iterating over 2 loops and the gcd function has a time complexity of log n.

Space Complexity:

The space complexity of this solution is O(n^2) because we are storing all possible fractions in the result list.

1