Leetcode 1447. Simplified Fractions

Problem Explanation

This problem asks us to return all the possible unique fractions that can be formed with the given input number as the maximum denominator.

Fractions are arithmetic expressions representing the division of two integers. It must be mentioned here that we are specifically looking for simplified fractions. In a simplified fraction, the numerator and the denominator are co-prime to each other and that their greatest common divisor is 1.

For example, if we take n as 2, the only possible simplified fraction that could be formed with the denominator less than or equal to 2 is "1/2".

Solution Approach

The given problem can be solved by the approach of iteration, involving nested for loops, and finding the greatest common divisor (GCD or sometimes also known as HCF-Highest Common Factor) of numerator and denominator.

• From denominator value equal to 2 to n, iterate for each number.
• For every iteration of denominator, iterate again from numberator value equal to 1 till denominator.
• For each iteration pair of numerator and denominator, find the gcd. If the gcd is 1, append the fraction of numerator/denominator to your answer list as gcd equal to 1 implies that the fraction is a simplified fraction.
• Finally, return the answer list containing all possible simplified fractions.

Solution

This is a simple solution using the iterative approach and leveraging the concept of GCD.

Python Solution

1
2python
3from math import gcd
4class Solution:
5    def simplifiedFractions(self, n: int):
6        ans = []
7        for denominator in range(2, n+1):
8            for numerator in range(1, denominator):
9                if gcd(numerator, denominator) == 1:
10                    ans.append(f"{numerator}/{denominator}")
11        return ans

Java Solution

1
2java
3class Solution {
4    public List<String> simplifiedFractions(int n) {
5        List<String> res = new ArrayList<>();
6        for (int denominator = 2; denominator <= n; denominator++) {
7            for (int numerator = 1; numerator < denominator; numerator++) {
8                if (gcd(numerator, denominator) == 1) {
9                    res.add(numerator + "/" + denominator);
10                }
11            }
12        }
13        return res;
14    }
15
16    private int gcd(int a, int b) {
17        if (b == 0) {
18                    return a;
19        }
20        return gcd(b, a % b);
21    }
22}

JavaScript Solution

1
2javascript
3class Solution {
4    simplifiedFractions(n) {
5        let res = [];
6        for (let denominator = 2; denominator <= n; denominator++) {
7            for (let numerator = 1; numerator < denominator; numerator++) {
8                if (this.gcd(numerator, denominator) === 1) {
9                    res.push(numerator + "/" + denominator);
10                }
11            }
12        }
13        return res;
14    }
15
16    gcd(a, b) {
17        if (b === 0) {
18            return a;
19        }
20        return this.gcd(b, a % b);
21    }
22}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<string> simplifiedFractions(int n) {
6        vector<string> ans;
7        for (int denominator = 2; denominator <= n; ++denominator)
8            for (int numerator = 1; numerator < denominator; ++numerator)
9                if (__gcd(denominator, numerator) == 1)
10                    ans.push_back(to_string(numerator) + "/" + to_string(denominator));
11        return ans;
12    }
13};

C# Solution

1
2csharp
3public class Solution {
4    public IList<string> SimplifiedFractions(int n) {
5        List<string> ans = new List<string>();
6        for (int denominator = 2; denominator <= n; ++denominator)
7            for (int numerator = 1; numerator < denominator; ++numerator)
8                if (GCD(denominator, numerator) == 1)
9                    ans.Add(numerator.ToString() + "/" + denominator.ToString());
10        return ans;
11    }
12
13    private int GCD(int a, int b) {
14        if (b == 0) return a;
15        return GCD(b, a % b);
16    }
17}

Final remarks

Please note that JavaScript and Python have in-built GCD functions but for the purpose of this explanation, we have written the function separately for better understanding. In real scenario, you can use the in-built functions for better performance.The above solutions have quite optimally utilized the nested loop structure for iteratively reaching each fraction and used a self-defined or built-in gcd function for checking the simplified fraction criteria.

However, there are a few ways we can look to optimize the solution.

Instead of iterating the numerator from 1 for every denominator, we can start iterating numerators from the last numerator value where gcd(numerator,denominator) is 1.

Another way is to recognize that fractions of the form a/(a+1) for a less than or equal to n will always generate a unique fraction and gcd will always be 1, and the non-repeated fractions will occur for any num less than a in the sequence. You will observe these fractions would always be in sequence and never repeated. Hence, we can smartly choose our denominator and numerator pairs to find simplified fractions without having the need of the gcd function at all.

Using these observations, below is the optimized python code.

Python Optimized Solution

1
2python
3class Solution:
4    def simplifiedFractions(self, n: int):
5        if n < 2: return []
6        ans, num = [], 1
7        for denominator in range(2, n+1):
8            if denominator % 2 == 0: num = 3
9            while num < denominator:
10                ans.append(f"{num}/{denominator}")
11                num += 2
12            num = 1
13        return ans

Similarly, you can adopt these techniques to modify the solutions provided in other languages. The solutions are quite simple and give us a good flavor of how gcd function is used for tackling such problems.

Remember that problem-solving involves not just knowing the core concepts, but also being aware of various ways to apply those concepts to arrive at the solution. This problem offered a way to revise gcd and its implementation, nested loop structure, and string functions.