#1447

Medium

LeetCode Problem Workspace

Simplified Fractions

Generate simplified fractions between 0 and 1 with denominators up to a given integer n.

Problem Statement

Given an integer n, return all simplified fractions between 0 and 1 (exclusive) where the denominator is less than or equal to n. Each fraction should be in the form of 'numerator/denominator' and you can return the list in any order.

A fraction is considered simplified if the greatest common divisor (GCD) of its numerator and denominator is 1. For example, '2/4' is not simplified because it can be reduced to '1/2'.

Examples

Example 1

Input: n = 2

Output: ["1/2"]

"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 details omitted.

Example 3

Input: n = 4

Output: ["1/2","1/3","1/4","2/3","3/4"]

"2/4" is not a simplified fraction because it can be simplified to "1/2".

Constraints

1 <= n <= 100

Solution Approach

Loop through possible fractions

For each denominator from 2 to n, iterate through all possible numerators (from 1 to denominator-1). Check if the GCD of the numerator and denominator is 1 to determine if the fraction is simplified.

Use GCD to simplify fractions

To efficiently check if a fraction is simplified, use the greatest common divisor (GCD) of the numerator and denominator. If the GCD is 1, the fraction is simplified.

Generate result as strings

For each valid simplified fraction, convert the numerator and denominator into a string of the form 'numerator/denominator' and append it to the result list.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of fractions generated, which is approximately O(n^2) due to the nested loops. For each fraction, checking the GCD takes constant time, and space complexity is also O(n^2) to store the fractions.

What Interviewers Usually Probe

Understanding of GCD and its application to fraction simplification
Ability to work with loops and basic string formatting
Familiarity with time and space complexity analysis in mathematical problems

Common Pitfalls or Variants

Common pitfalls

Forgetting to check the GCD of the numerator and denominator to ensure the fraction is simplified
Generating fractions in the wrong order or including fractions like '2/4' that aren't simplified
Not handling edge cases, such as when n is 1 (which would not result in any simplified fractions)

Follow-up variants

Modify the problem to return fractions in ascending order by value
Return only fractions where the numerator is prime
Optimize the solution by using a sieve approach to identify valid fractions

FAQ

How can I generate all simplified fractions for a given n?

Loop through each denominator from 2 to n and check every possible numerator. Use the GCD to determine if the fraction is simplified.

What is a simplified fraction?

A fraction is simplified if the greatest common divisor (GCD) of the numerator and denominator is 1.

What is the time complexity of solving this problem?

The time complexity is approximately O(n^2) due to the nested loops and GCD checks for each fraction.

What is the primary pattern in this problem?

The primary pattern involves math (GCD and fractions) combined with string manipulation to output the result.

How do I handle fractions like '2/4' that are not simplified?

By checking the GCD of the numerator and denominator, you can avoid adding unsimplified fractions to the result.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

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

Continue Practicing

#1492 the kth factor of n #1513 number of substrings with only 1s #1360 number of days between two dates