Valizada's blog

1447 Simplified Fractions, Leetcode

1447 Simplified fractions

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. The fractions can be in any order. Examples:

  1. Input: n = 2 Output: ["1/2"] Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
  2. Input: n = 3 Output: ["1/2","1/3","2/3"]
  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".

Lets have a look at this table and see if we can observe a pattern:

N Result
1 Empty list
2 ["1/2"]
3 ["1/2","1/3","2/3"]
4 ["1/2","1/3","2/3", "1/4",,"3/4"]

Did you spot the pattern? - On every next N we use the list from N-1 plus simplified fractions with N as the denominator. This can be solved with a simple recursion with base case of check for 1:

  1. If 1, return empty list
  2. Else, calculate fractions for N
  3. Add fractions of N-1
    public List<String> simplifiedFractions(int n) {
        if(n == 1) {
            return new ArrayList<>();
        }
        
        var list = fractions(n);
        
        list.addAll(simplifiedFractions(n-1));
        return list;
    }

Now, the next challenge is to actually find simplified fractions. For example, if denominator N is 3, then it is easy just start from 1 as numerator and iterate till N-1: 1/3, 2/3

It gets trickier for 4, if we follow the same approach as above we get: 1/4, 2/4, 3/4

As we can see this approach fails as 2/4 is not simplified. So, how do we get simplified fractions? - By dividing denominator and numerator by their GCD (greatest common divisor). If GCD is 1, then we have the simplified version.

Here is how we calculate fractions for N. Iterate over all possible numerators and add to list only if GCD is 1.

    private List<String> fractions(int n) {
        var list = new ArrayList<String>();
        for(int numerator = 1; numerator < n; numerator++) {
            if(gcd(numerator, n) == 1) {
                list.add(numerator + "/" + n);
            }
        }
        return list;
    }

And last part is, how do we find GCD itself. It is another recursion where we just keep dividing digits by each other till we get 0.

    private int gcd(int a, int b) {
        if(a == 0) {
            return b;
        }
        return gcd(b%a, a);
    }

Here is complete piece of code:

class Solution {
    
    public List<String> simplifiedFractions(int n) {
        if(n == 1) {
            return new ArrayList<>();
        }
        
        var list = fractions(n);
        
        list.addAll(simplifiedFractions(n-1));
        return list;
    }
    
    private List<String> fractions(int n) {
        var list = new ArrayList<String>();
        for(int numerator = 1; numerator < n; numerator++) {
            if(gcd(numerator, n) == 1) {
                list.add(numerator + "/" + n);
            }
        }
        return list;
    }
    
    private int gcd(int a, int b) {
        if(a == 0) {
            return b;
        }
        return gcd(b%a, a);
    }
}