Jobs

Interviews

Discussions

Simplified Fractions

Medium

Google

1 view

Topics:

ArraysStrings

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. You can return the answer in any order. A fraction is simplified if the greatest common divisor (GCD) of its numerator and denominator is 1.

For example:

If n = 2, the output should be ["1/2"]. This is because "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
If n = 3, the output should be ["1/2","1/3","2/3"].
If n = 4, the output should be ["1/2","1/3","1/4","2/3","3/4"]. Note that "2/4" is not a simplified fraction because it can be simplified to "1/2".

How would you approach this problem, considering efficiency and the constraints 1 <= n <= 100?

Simplified Fractions

Medium

Google

1 view

Topics:

ArraysStrings

For example:

If n = 2, the output should be ["1/2"]. This is because "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
If n = 3, the output should be ["1/2","1/3","2/3"].
If n = 4, the output should be ["1/2","1/3","1/4","2/3","3/4"]. Note that "2/4" is not a simplified fraction because it can be simplified to "1/2".

How would you approach this problem, considering efficiency and the constraints 1 <= n <= 100?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range for the numerator and denominator? Should I expect negative numbers or zero?
Should the returned list of fractions be in any specific order?
If the numerator and denominator are the same (e.g., 2/2), should I simplify it to '1/1' or '1'?
Are the numerator and denominator guaranteed to be integers?
If there are no simplified fractions (other than those equal to 0/1), what should the function return?

Brute Force Solution

Approach

The brute force approach to finding simplified fractions means we're going to try every possible fraction and check if it meets our criteria. We'll generate all fractions within the given range and then determine which ones are in their simplest form.

Here's how the algorithm would work step-by-step:

First, let's generate every possible fraction using all numbers within the given range. This means for every number as the top part of the fraction, we try every number as the bottom part of the fraction.
Now, for each fraction we created, we need to check if it's simplified. A simplified fraction is one where the top and bottom parts have no common divisors other than 1.
To check if a fraction is simplified, find the greatest common divisor (GCD) of the top and bottom parts.
If the greatest common divisor is 1, the fraction is already in its simplest form, so we keep it.
If the greatest common divisor is not 1, the fraction can be simplified further, so we discard it or don't include it in our final set of simplified fractions.
After checking all possible fractions, we'll have a list of only the simplified fractions within the range.

Code Implementation

def simplified_fractions(integer_number):
    simplified_fraction_list = []
    for numerator in range(1, integer_number + 1):
        for denominator in range(1, integer_number + 1):
            # Avoid division by zero
            if denominator != 0:

                # Calculate the greatest common divisor
                greatest_common_divisor = calculate_greatest_common_divisor(numerator, denominator)

                # Check if the fraction is simplified
                if greatest_common_divisor == 1:

                    #Ensures no duplicates and no fractions > 1, simplifies problem per prompt.
                    if numerator <= denominator:
                        simplified_fraction_list.append(f'{numerator}/{denominator}')
    return simplified_fraction_list

def calculate_greatest_common_divisor(first_number, second_number):
    #Euclid's algorithm to find the GCD, works by recursion
    while(second_number):
        first_number, second_number = second_number, first_number % second_number
    return first_number

Big(O) Analysis

Time Complexity

O(n^2 * log(n)) – The algorithm iterates through all possible numerators and denominators from 1 to n, resulting in n*n = n^2 fraction combinations. For each fraction, the algorithm calculates the greatest common divisor (GCD) using the Euclidean algorithm, which takes O(log(min(numerator, denominator))) time. In the worst case, the GCD calculation takes O(log(n)) time. Therefore, the overall time complexity is O(n^2 * log(n)).

Space Complexity

O(N^2) – The algorithm generates every possible fraction within the given range [1, N], where N is the upper bound. This implies potentially storing all simplified fractions found. In the worst-case scenario, a significant proportion of these N^2 fractions could be simplified, requiring space to store them. Therefore, the space complexity is proportional to the number of possible fractions considered, which is O(N^2).

Optimal Solution

Approach

The key to solving this problem efficiently is finding the greatest common divisor (GCD) of the numerator and denominator. Once we find the GCD, we can simplify the fraction. By systematically checking all possible fractions, we can collect the simplified results.

Here's how the algorithm would work step-by-step:

Start by considering all possible fractions where the numerator and denominator are within the given range.
For each fraction, find the largest number that divides both the numerator and denominator evenly (this is the GCD). A simple way is to repeatedly subtract the smaller number from the larger one until they are equal. That remaining number is the GCD.
Divide both the numerator and denominator by their GCD to get the simplest form of the fraction.
Store each simplified fraction as a string. Make sure you avoid duplicates.
Once you've checked all possible fractions, return the list of simplified fractions.

Code Implementation

def simplified_fractions(maximum_denominator):
    simplified_fractions_set = set()
    result = []

    for numerator in range(1, maximum_denominator + 1):
        for denominator in range(numerator + 1, maximum_denominator + 1):

            # Use GCD to find the greatest common divisor.
            numerator_copy = numerator
            denominator_copy = denominator

            while denominator_copy:
                numerator_copy, denominator_copy = denominator_copy, numerator_copy % denominator_copy

            greatest_common_divisor = numerator_copy

            simplified_numerator = numerator // greatest_common_divisor
            simplified_denominator = denominator // greatest_common_divisor

            # Check for duplicates
            fraction_string = str(simplified_numerator) + "/" + str(simplified_denominator)

            if fraction_string not in simplified_fractions_set:
                # Store the fraction string to avoid duplicates
                simplified_fractions_set.add(fraction_string)
                result.append(fraction_string)

    return result

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible fractions, where both the numerator and denominator are up to n. This creates a nested loop structure resulting in O(n²) iterations. Inside the loops, calculating the GCD using repeated subtraction can take up to O(n) in the worst case, but since GCD calculation happens within the O(n²) loops, and GCD calculation is proportional to n but independent of the outer n^2 operations, we ignore it. Storing the simplified fractions and checking for duplicates could take additional time, but these operations are performed within the dominant O(n²) loops, so the overall time complexity remains O(n²).

Space Complexity

O(N^2) – The algorithm iterates through all possible fractions where the numerator and denominator are within the range of 1 to N. The simplified fractions are stored to avoid duplicates. In the worst case, almost all fractions could be unique and simplified. Therefore, the space complexity is driven by the storage of simplified fractions as strings, which in the worst case could approach O(N^2), specifically for storing the numerator and denominator combinations as strings.

Edge Cases

Case	How to Handle
n = 1	Return an empty list since no fractions are possible with only one number.
n = 2 (minimum valid input)	The solution should correctly identify and return the single reduced fraction.
Input includes zero (0 as denominator)	Division by zero should be avoided; skip the fraction if the denominator is 0.
Duplicate fractions exist before reduction (e.g., 2/4 and 1/2)	Use a set to store the string representation of reduced fractions and prevent duplicates.
Integer overflow in numerator or denominator during GCD calculation or fraction construction with large n	Use appropriate data types (e.g., long) and check for potential overflow during calculation.
Negative input values	Handle negative signs appropriately, reducing fractions to their standard form (negative sign on numerator or none if both are negative).
Large n (performance considerations)	GCD calculation should be optimized for efficiency; the overall complexity will still be at least O(n^2 * log(max_val)), but minimize constant factors.
All fractions simplify to the same value	The set should correctly handle adding multiple instances of the same simplified fraction string, effectively storing only one.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range for the numerator and denominator? Should I expect negative numbers or zero?
Should the returned list of fractions be in any specific order?
If the numerator and denominator are the same (e.g., 2/2), should I simplify it to '1/1' or '1'?
Are the numerator and denominator guaranteed to be integers?
If there are no simplified fractions (other than those equal to 0/1), what should the function return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, let's generate every possible fraction using all numbers within the given range. This means for every number as the top part of the fraction, we try every number as the bottom part of the fraction.
Now, for each fraction we created, we need to check if it's simplified. A simplified fraction is one where the top and bottom parts have no common divisors other than 1.
To check if a fraction is simplified, find the greatest common divisor (GCD) of the top and bottom parts.
If the greatest common divisor is 1, the fraction is already in its simplest form, so we keep it.
If the greatest common divisor is not 1, the fraction can be simplified further, so we discard it or don't include it in our final set of simplified fractions.
After checking all possible fractions, we'll have a list of only the simplified fractions within the range.

Code Implementation

def simplified_fractions(integer_number):
    simplified_fraction_list = []
    for numerator in range(1, integer_number + 1):
        for denominator in range(1, integer_number + 1):
            # Avoid division by zero
            if denominator != 0:

                # Calculate the greatest common divisor
                greatest_common_divisor = calculate_greatest_common_divisor(numerator, denominator)

                # Check if the fraction is simplified
                if greatest_common_divisor == 1:

                    #Ensures no duplicates and no fractions > 1, simplifies problem per prompt.
                    if numerator <= denominator:
                        simplified_fraction_list.append(f'{numerator}/{denominator}')
    return simplified_fraction_list

def calculate_greatest_common_divisor(first_number, second_number):
    #Euclid's algorithm to find the GCD, works by recursion
    while(second_number):
        first_number, second_number = second_number, first_number % second_number
    return first_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering all possible fractions where the numerator and denominator are within the given range.
For each fraction, find the largest number that divides both the numerator and denominator evenly (this is the GCD). A simple way is to repeatedly subtract the smaller number from the larger one until they are equal. That remaining number is the GCD.
Divide both the numerator and denominator by their GCD to get the simplest form of the fraction.
Store each simplified fraction as a string. Make sure you avoid duplicates.
Once you've checked all possible fractions, return the list of simplified fractions.

Code Implementation

def simplified_fractions(maximum_denominator):
    simplified_fractions_set = set()
    result = []

    for numerator in range(1, maximum_denominator + 1):
        for denominator in range(numerator + 1, maximum_denominator + 1):

            # Use GCD to find the greatest common divisor.
            numerator_copy = numerator
            denominator_copy = denominator

            while denominator_copy:
                numerator_copy, denominator_copy = denominator_copy, numerator_copy % denominator_copy

            greatest_common_divisor = numerator_copy

            simplified_numerator = numerator // greatest_common_divisor
            simplified_denominator = denominator // greatest_common_divisor

            # Check for duplicates
            fraction_string = str(simplified_numerator) + "/" + str(simplified_denominator)

            if fraction_string not in simplified_fractions_set:
                # Store the fraction string to avoid duplicates
                simplified_fractions_set.add(fraction_string)
                result.append(fraction_string)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 1	Return an empty list since no fractions are possible with only one number.
n = 2 (minimum valid input)	The solution should correctly identify and return the single reduced fraction.
Input includes zero (0 as denominator)	Division by zero should be avoided; skip the fraction if the denominator is 0.
Duplicate fractions exist before reduction (e.g., 2/4 and 1/2)	Use a set to store the string representation of reduced fractions and prevent duplicates.
Integer overflow in numerator or denominator during GCD calculation or fraction construction with large n	Use appropriate data types (e.g., long) and check for potential overflow during calculation.
Negative input values	Handle negative signs appropriately, reducing fractions to their standard form (negative sign on numerator or none if both are negative).
Large n (performance considerations)	GCD calculation should be optimized for efficiency; the overall complexity will still be at least O(n^2 * log(max_val)), but minimize constant factors.
All fractions simplify to the same value	The set should correctly handle adding multiple instances of the same simplified fraction string, effectively storing only one.