Simplified Fractions Solution in Python

Problem Description

Welcome to the world of fractions, where numbers are divided and conquered! The problem at hand is to generate all simplified fractions for a given integer n. You might be wondering, “What’s a simplified fraction?” Well, it’s like that one friend who always tries to keep things simple—no unnecessary complexity, just the pure essence of a fraction.

Imagine you’re at a pizza party (who doesn’t love pizza?), and you want to share slices with your friends. You can’t just cut the pizza into random pieces; you need to make sure each piece is a simplified fraction of the whole pizza. So, if you have 3 slices out of 4, that’s a simplified fraction! But if you have 2 slices out of 4, you might as well just say you have half a pizza.

In this problem, you’ll be tasked with generating all such simplified fractions for every possible denominator from 2 to n.

Code Solution

import math

class Solution:
    def simplifiedFractions(self, n: int) -> list[str]:
        ans = []
        for denominator in range(2, n + 1):
            for numerator in range(1, denominator):
                if math.gcd(denominator, numerator) == 1:
                    ans.append(str(numerator) + '/' + str(denominator))
        return ans

Approach

The approach here is straightforward yet elegant. We loop through each denominator from 2 to n and for each denominator, we loop through all possible numerators. The key is to check if the greatest common divisor (GCD) of the numerator and denominator is 1. If it is, we know that the fraction is simplified, and we can add it to our list of results.

Time and Space Complexity

• Time Complexity: O(n²) – We have two nested loops, one for the denominator and one for the numerator.
• Space Complexity: O(n) – The space used is primarily for storing the resulting list of simplified fractions.

Real-World Example

Let’s say you’re at a cooking class, and the instructor asks you to measure out ingredients for a recipe. You have a cup that can hold 4 ounces of flour, but you only need 3 ounces. Instead of saying you need 3/4 of a cup, you can simply say you need 3 ounces. This is the essence of simplified fractions—keeping things clear and straightforward!