Minimum score of one question per day

1447. Simplest fraction

Medium difficulty

Give you an integer  n , Please return to all 0 To 1 Between （ barring 0 and 1） Satisfy that the denominator is less than or equal to   n  Of   Simplest   fraction  . The score can be in the form of   arbitrarily   Sequential return .

Example 1：

Input ：n = 2 Output ：["1/2"] explain ："1/2" Is the only denominator less than or equal to 2 The simplest fraction of .

Example 2：

Input ：n = 3 Output ：["1/2","1/3","2/3"]

Example 3：

Input ：n = 4 Output ：["1/2","1/3","1/4","2/3","3/4"] explain ："2/4" It's not the simplest fraction , Because it can be reduced to "1/2" .

Example 4：

Input ：n = 1 Output ：[]

Tips ：

• 1 <= n <= 100

Pass times 22,357

Submit the number 33,159

 Java

``` 

class Solution {
    public List<String> simplifiedFractions(int n) {
        List<String> ans = new ArrayList<String>();
        for (int denominator = 2; denominator <= n; ++denominator) {
            for (int numerator = 1; numerator < denominator; ++numerator) {
                if (gcd(numerator, denominator) == 1) {
                    ans.add(numerator + "/" + denominator);
                }
            }
        }
        return ans;
    }

    public int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}

python

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