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)