Teaching Kids Programming – Math Simplified Fractions where Denominator is Less-than-or-equal-to N

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Example 1:
Input: n = 2
Output: [“1/2”]
Explanation: “1/2” is the only unique fraction with a denominator less-than-or-equal-to 2.

Example 2:
Input: n = 3
Output: [“1/2″,”1/3″,”2/3”]

Example 3:
Input: n = 4
Output: [“1/2″,”1/3″,”1/4″,”2/3″,”3/4”]
Explanation: “2/4” is not a simplified fraction because it can be simplified to “1/2”.

Hints:
A fraction is fully simplified if there is no integer that divides cleanly into the numerator and denominator.
In other words the greatest common divisor of the numerator and the denominator of a simplified fraction is 1.

Simplified Fractions Algorithm

A fraction is simplified if the denominator and numerator is comprime aka the greatest common divisor is 1.

1
2
3
4
5
6
7
8

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

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

The time complexity of the GCD is and therefore overall time complexity is

–EOF (The Ultimate Computing & Technology Blog) —