Leetcode 1447: Simplified Fractions

In this Leetcode problem, we are going to list all the simplified fractions with denominator d ≤ n , with n input.

Problem statement

Solution

We first notice that for each denominator, the results are distinct, and therefore recursively:

simplifiedFractions(n + 1) = simplifiedFractions(n)
    + number of simplified fractions with denominator (n + 1)

To save a little bit of space, we can simply do a for loop in which we compute all the simplified fractions for each denominator.

To find the simplified fractions for denominator n, we try
1/n, 2/n,…, (n-1)/n. To find out if these are simplified, we compute gcd(i,n) for all 1 ≤ i < n.

Here is the full code for reference:

class Solution {
    public List<String> simplifiedFractions(int n) {
        List<String> res = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (gcd(i, j) == 1) {
                    res.add(j + "/" + i);
                }
            }
        }
        return res;
    }
    
    int gcd(int i, int j) {
        int p = i % j;
        if (p == 0) {
            return j;
        }
        return gcd(j, p);
    }
}

Happy coding :)

What’s next:

• Checkout the solution for another problem: Consecutive characters
• Contact me: poitevinpm@gmail.com
• Looking to interview for a software engineer position? Contact me :)