Generate Fractions Blackstone Python Interview Question

Given an integer , generate all simplified fractions between and (exclusive) where the denominator is less than or equal to . A fraction is simplified if the numerator and denominator have no common divisors other than .

Return a sorted list of fractions, where each fraction is represented as .

For example:

• If $n = 3$, return [[1, 2], [1, 3], [2, 3]]
• If $n = 4$, return [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4]]
• If $n = 5$, return [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 5], [3, 4], [3, 5], [4, 5]]

Brute Force Solution

The simplest way to generate all unique fractions between and with denominators up to is to use two nested loops to iterate through all possible numerators and denominators. For each fraction, we simplify it and only store unique results. Here’s how this approach works:

1. Use a loop to iterate through possible numerators from to .
2. For each numerator, loop through possible denominators starting from to . By setting the denominator to be greater than the numerator, we ensure the fraction is less than .
3. For each fraction, we use the function from Python’s module to find the greatest common divisor (GCD) of the numerator and denominator. We then divide both by this GCD to get the fraction in its simplest form.
4. To keep only unique fractions, we use a set to store each simplified fraction as a tuple. Checking if a fraction already exists in a set is efficient with $O(1)$ time complexity.
5. Since we iterate in ascending order of numerators and denominators, our list of fractions will naturally be in sorted order, so there’s no need for further sorting.

Here’s the code:

Please note: Some interviewer's may let you first write the solution using the function, but then force you to code it up manually without importing it. Be prepared to have to code this up!

Space-Optimized Approach

To further optimize this approach, we can avoid using a set by only adding fractions that are already in their simplest form. If a fraction has a GCD of , it means the fraction is in its simplest form, so we don’t need to simplify or check for duplicates. Here’s how it works:

1. Loop through numerators from up to and denominators from to .
2. For each fraction, use the function from Python’s module to check if the GCD of the numerator and denominator is . If it is, the fraction is already in its simplest form, so we add it directly to the result.

This avoids duplicate fractions without the need for a set. Additionally, because we are iterating from smaller to larger numerators and denominators, the fractions remain in ascending order, eliminating the need for additional sorting.

Whenever a fraction isn’t in its simplest form (i.e., its GCD is greater than ), simplifying it will yield an equivalent fraction where both the numerator and denominator are smaller. This simplified version would already have been explored earlier in the loop since we iterate from the smallest numerators and denominators upwards.

For example, consider the fraction . Its GCD is , so we can simplify it by dividing both the numerator and denominator by :

• Simplified numerator: $\frac{4}{2} = 2$
• Simplified denominator: $\frac{6}{2} = 3$
• This results in the equivalent fraction .

Since we loop through numerators and denominators in ascending order, we would encounter (already in its simplest form) before reaching . By only adding fractions with a GCD of , we ensure that simplified versions like are already included in the result by the time we reach non-simplified ones like . This way, we avoid both unnecessary simplification and the need to check for duplicates.

Here’s the code: