1447. Simplified Fractions

MediumMathStringNumber Theory

Problem Description

In this problem, we are given an integer n and we need to find all unique fractions where the numerator (top number) is less than the denominator (bottom number), the denominator is between 2 and n, and the fraction is in its simplest form. A fraction is in its simplest form if the greatest common divisor (GCD) of its numerator and denominator is 1, meaning the fraction cannot be reduced any further. We need to list the fractions that are in between (but not including) 0 and 1, which means the numerator will always be less than the denominator. The output should be a list of these fractions represented as strings and they can be in any order.

Intuition

To solve this problem, we use a nested loop approach where we iterate through all possible numerators (i) and denominators (j).

We initiate the outer loop with i starting from 1 to n - 1. The numerator must be less than the denominator, hence it is less than n.
We begin the inner loop with j starting from i + 1 to n. The reason j starts at i + 1 is to ensure that we always have a fraction (since i is less than j), and to make sure the denominator is greater than the numerator for valid fractions between 0 and 1.
For every combination of (i, j) we check if the GCD of i and j is 1. This check is performed using the gcd function. If it is 1, then the fraction (i/j) is in its simplest form and can be included in our list.
If the GCD is 1, we create a string representation of the fraction by using string formatting, so i and j are inserted into the string in the form '{i}/{j}'.
All the fractions that meet the condition are collected into a list using list comprehension and returned as the final answer.

The use of the embedded loops is suitable here because we need to compare each possible numerator with each possible denominator, and we require this comprehensive checking to ensure that we don't miss any simplified fractions.

Learn more about Math patterns.

Solution Approach

The solution to this problem follows a direct brute-force approach, by iterating over the range of possible numerators and denominators, then checking for their simplicity before including them in the results. Below is a step-by-step breakdown of the implementation strategy.

List Comprehension: The entire implementation utilizes Python's list comprehension, which is a concise way to create lists. It allows us to iterate over an iterable, apply a filter or condition, and process the items, all in a single, readable line.
Nested Loops: We make use of nested loops within the list comprehension. The outer loop iterates over all possible numerators i from 1 up to n-1. The inner loop iterates over all possible denominators j from i+1 up to n. This ensures we only consider fractions where the numerator is less than the denominator.
Greatest Common Divisor (GCD): To ensure that we only take the simplified fractions (irreducible fractions), we check the GCD of the numerator and denominator. The gcd function from Python's standard library (usually from [math](/problems/math-basics) module, though not explicitly shown in the code provided) calculates the GCD. If gcd(i, j) equals 1, it means i and j are coprime and thus the fraction i/j is already in its simplest form.
String Formatting: For each fraction that is in simplified form, we format the numerator and denominator into a string of the form 'i/j'. This is done using an f-string f'{i}/{j}', which is a way to embed expressions inside string literals using curly braces.
Output: The output is a list of these formatted string representations of all simplified fractions for the given n.

No additional data structures or complex patterns are used here. The simplicity of this solution is its strength, as it directly answers the need without unnecessary complications, making full use of Python's built-in functionalities to handle the problem in an efficient and understandable manner.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example with n = 5.

We start with an empty list to hold our results.
The outer loop will run with i starting from 1 to 4 (since i ranges from 1 to n - 1, which is 5 - 1).
For each i, the inner loop will run with j starting from i + 1, up to 5 (n).

We will go through iterations like this:

For i = 1:
- j will range from 2 to 5. So we will check the fractions 1/2, 1/3, 1/4, and 1/5.
- All these fractions are in their simplest forms, so all of them will be added to the results list.
For i = 2:
- j will range from 3 to 5. We will check the fractions 2/3, 2/4, and 2/5.
- 2/3 and 2/5 are in their simplest forms, so they will be added.
- 2/4 can be reduced to 1/2 (which is already included), hence, it will not be added.
For i = 3:
- j will range from 4 to 5. We check 3/4 and 3/5.
- Both fractions are in their simplest forms and will be added to the results list.
For i = 4:
- j is 5. We check 4/5.
- 4/5 is already in its simplest form, so it gets added.

Finally, the results list would consist of all the fractions in their simplest forms within the range 1/i to 4/5, which are: 1/2, 1/3, 1/4, 1/5, 2/3, 2/5, 3/4, and 4/5.

As assured by the solution approach, no fractions are repeated, and all are in the simplest form. This approach leverages the power of list comprehension paired with nested loops and GCD checks in Python to effectively gather the results.

Solution Implementation

1from typing import List
2from math import gcd
3
4class Solution:
5    def simplifiedFractions(self, n: int) -> List[str]:
6        # List comprehension to generate simplified fractions
7        return [
8            f'{numerator}/{denominator}'  # format as a fraction
9            for numerator in range(1, n)           # loop over numerators
10            for denominator in range(numerator + 1, n + 1)  # loop over denominators
11            if gcd(numerator, denominator) == 1  # include fraction if gcd is 1 i.e., fractions are simplified
12        ]
13
14# Example of how to use the class:
15# sol = Solution()
16# print(sol.simplifiedFractions(4))  # Output: ['1/2', '1/3', '1/4', '2/3', '3/4']
17

1class Solution {
2    // Generates a list of simplified fractions less than 1 for a given integer n
3    public List<String> simplifiedFractions(int n) {
4        // List to hold the result of simplified fractions
5        List<String> fractions = new ArrayList<>();
6      
7        // Loop over all possible numerators
8        for (int numerator = 1; numerator < n; ++numerator) {
9            // Loop over all possible denominators greater than the numerator
10            for (int denominator = numerator + 1; denominator <= n; ++denominator) {
11                // Add the fraction to the list if the numerator and denominator are coprime
12                if (gcd(numerator, denominator) == 1) {
13                    fractions.add(numerator + "/" + denominator);
14                }
15            }
16        }
17        return fractions;
18    }
19
20    // Helper method to calculate the greatest common divisor (GCD) using Euclid's algorithm
21    private int gcd(int a, int b) {
22        // Recursively compute gcd, with the base case being when b is 0
23        return b > 0 ? gcd(b, a % b) : a;
24    }
25}
26

1#include <vector>
2#include <string>
3#include <algorithm> // for std::gcd
4using namespace std;
5
6class Solution {
7public:
8    // Generates a list of simplified fractions for denominators up to 'maxDenominator'
9    vector<string> simplifiedFractions(int maxDenominator) {
10        vector<string> simplifiedFractionsList; // Stores the list of simplified fractions
11      
12        // Iterate over all possible numerators
13        for (int numerator = 1; numerator < maxDenominator; ++numerator) {
14            // Iterate over all possible denominators
15            for (int denominator = numerator + 1; denominator <= maxDenominator; ++denominator) {
16                // Check if the fraction is in simplest form (gcd is 1)
17                if (gcd(numerator, denominator) == 1) {
18                    // Concatenate the parts of the fraction into a string
19                    simplifiedFractionsList.push_back(to_string(numerator) + "/" + to_string(denominator));
20                }
21            }
22        }
23        // Return the list of simplified fractions
24        return simplifiedFractionsList;
25    }
26};
27

1/**
2 * Returns an array of simplified fractions up to a given limit.
3 * @param {number} maxDenominator - The maximum denominator to consider for the fractions.
4 * @returns {string[]} - An array of strings representing simplified proper fractions.
5 */
6function simplifiedFractions(maxDenominator: number): string[] {
7    // Initialize an array to hold the simplified fractions.
8    const fractions: string[] = [];
9    // Loop over all possible numerators.
10    for (let numerator = 1; numerator < maxDenominator; ++numerator) {
11        // Loop over all possible denominators greater than the numerator.
12        for (let denominator = numerator + 1; denominator <= maxDenominator; ++denominator) {
13            // Check if the fraction is already in simplest form.
14            if (gcd(numerator, denominator) === 1) {
15                // If so, add the fraction to the array.
16                fractions.push(`${numerator}/${denominator}`);
17            }
18        }
19    }
20    // Return the array of simplified fractions.
21    return fractions;
22}
23
24/**
25 * Calculates the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.
26 * @param {number} a - The first number.
27 * @param {number} b - The second number.
28 * @returns {number} - The GCD of the two numbers.
29 */
30function gcd(a: number, b: number): number {
31    // Base case: if the second number is 0, the GCD is the first number.
32    return b === 0 ? a : gcd(b, a % b);
33}
34

Time and Space Complexity

Time Complexity

The time complexity of the code is calculated by considering the nested for-loops and the call to gcd (Greatest Common Divisor) function for each combination.

The outer loop runs from 1 to n - 1 which gives us n - 1 iterations.
The inner loop runs from i + 1 to n for each value of i from the outer loop. In the worst case, the inner loop runs n/2 times on average (since starting point increases as i increases).
The gcd function can be assumed to run in O(log(min(i, j))) in the worst case, which is generally due to the Euclidean algorithm for computing the greatest common divisor.

Therefore, the time complexity is approximately O(n^2 * log(n)). However, this is an upper bound; the average case might be lower due to early termination of the gcd calculations for most pairs.

Space Complexity

The space complexity is determined by the space required to store the output list. In the worst case scenario, the number of simplified fractions is maximized when n is a prime number, resulting in a list of size 1/2 * (n - 1) * (n - 2) (since each number from 1 to n - 1 will be paired with every number greater than it up to n).

Thus, the space complexity of the solution is O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: