Jobs

Interviews

Discussions

Fraction to Recurring Decimal

Medium

Asked by:

16 views

Topics:

StringsArrays

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10⁴ for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Constraints:

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

Fraction to Recurring Decimal

Medium

Asked by:

16 views

Topics:

StringsArrays

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10⁴ for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Constraints:

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

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:

Can the numerator and denominator be negative or zero?
What is the expected output if the decimal representation is a non-recurring decimal (i.e., it terminates)? Should I still format it as a string?
What is the maximum possible value for the numerator and denominator, and should I be concerned about integer overflow during calculations?
If the denominator is zero, should I throw an exception or return a specific error string/value?
Are there any specific formatting requirements for the repeating decimal portion (e.g., using parentheses)? If so, what should be returned if the repeating portion has leading zeros?

Brute Force Solution

Approach

The brute force approach to converting a fraction to a decimal involves performing long division by hand, digit by digit. We repeatedly find the quotient and remainder at each step, keeping track of the remainders we've seen. If a remainder repeats, the decimal part repeats from that point onward.

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

Start by performing long division of the numerator by the denominator.
Calculate the whole number part of the division.
If the numerator is now zero, then the decimal representation terminates and we're done.
If the numerator is not zero, start tracking the remainders we get at each step.
Multiply the remainder by 10 (as you would in long division) and perform the division again to get the next decimal digit.
Check if the new remainder we calculated already exists in our list of tracked remainders.
If the remainder is in the list, this means we've found a repeating part. The decimal representation between the first occurrence of the remainder and its second occurrence is the repeating part.
If the remainder is NOT in the list, then add it to our list and continue the division process by going back to multiplying the remainder by 10.
Keep doing the long division and tracking the remainders until either the remainder becomes zero (the decimal terminates) or you find a repeating remainder (the decimal repeats).

Code Implementation

def fraction_to_recurring_decimal(numerator, denominator):
    if numerator == 0:
        return "0"

    sign = "-" if (numerator < 0) ^ (denominator < 0) else ""
    numerator = abs(numerator)
    denominator = abs(denominator)

    whole_number_part = numerator // denominator
    remainder = numerator % denominator

    if remainder == 0:
        return sign + str(whole_number_part)

    decimal_part = ""
    remainders_seen = {}

    while remainder != 0 and remainder not in remainders_seen:
        # Store the current remainder and its index in decimal_part
        remainders_seen[remainder] = len(decimal_part)

        remainder *= 10
        decimal_part += str(remainder // denominator)
        remainder %= denominator

    if remainder == 0:
        return sign + str(whole_number_part) + "." + decimal_part
    else:
        # Repeating part found; insert parentheses
        insert_position = remainders_seen[remainder]
        decimal_part = decimal_part[:insert_position] + "(" + 
                       decimal_part[insert_position:] + ")"

        return sign + str(whole_number_part) + "." + decimal_part

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the length of the repeating decimal, which in the worst case can be proportional to the denominator (n). The while loop continues until either the remainder becomes zero or a repeating remainder is found. In each iteration, we perform constant-time operations (multiplication, division, and checking for existence in the hash map). The hash map lookups take constant time on average. Therefore, in the worst case scenario where all the remainders are unique before repeating, the number of iterations is bounded by n, hence the time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a hash map (or similar data structure) to track the remainders encountered during the long division process. In the worst-case scenario, where the decimal representation doesn't repeat quickly or terminates after many digits, the hash map could potentially store up to N remainders, where N is related to the magnitude of the denominator. Therefore, the auxiliary space required for storing the remainders can grow linearly with N. Thus the space complexity is O(N).

Optimal Solution

Approach

To convert a fraction to a decimal, we perform long division. When the remainder repeats during division, the decimal part also repeats, indicating a recurring decimal. We use a map to detect repeating remainders, which allows us to efficiently determine the repeating part.

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

First, handle the sign of the result. If either the numerator or denominator is negative (but not both), the result is negative.
Convert both the numerator and denominator to positive values to simplify the division process.
Calculate the integer part of the decimal by performing integer division.
Find the remainder after the integer division.
If the remainder is zero, the fraction results in a whole number; we're done.
If the remainder is not zero, start building the decimal part.
Use a map (or dictionary) to store remainders we've already seen, along with the position (index) where we saw them.
In a loop, multiply the remainder by 10 and perform integer division again. This gives the next digit of the decimal.
Check if the new remainder is already in the map. If it is, this indicates the start of the repeating part of the decimal. Insert parentheses around the repeating part.
If the remainder is not in the map, store it along with its current position and continue the loop.
If the remainder becomes zero, the decimal terminates, and we're done.
Return the result, which consists of the integer part, a decimal point, the non-repeating part of the decimal, and the repeating part (if any) enclosed in parentheses.

Code Implementation

def fraction_to_recurring_decimal(numerator, denominator):
    if numerator == 0:
        return "0"

    sign = "-" if (numerator < 0) ^ (denominator < 0) else ""
    numerator = abs(numerator)
    denominator = abs(denominator)

    integer_part = numerator // denominator
    remainder = numerator % denominator

    if remainder == 0:
        return sign + str(integer_part)

    decimal_part = ""
    remainder_map = {}

    while remainder != 0:
        # If the remainder repeats, we have found the repeating part
        if remainder in remainder_map:
            index = remainder_map[remainder]
            decimal_part = decimal_part[:index] + "(" + decimal_part[index:] + ")"
            break

        remainder_map[remainder] = len(decimal_part)
        remainder *= 10
        decimal_part += str(remainder // denominator)
        remainder %= denominator

    return sign + str(integer_part) + "." + decimal_part

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The core of the algorithm involves long division, and the critical aspect affecting time complexity is the detection of repeating remainders. A hash map (or dictionary) is used to store remainders and their positions. In the worst case, we might need to perform a division step for each digit in the non-repeating and repeating parts of the decimal representation. The number of such digits can be, at most, proportional to the denominator n. Since hash map lookups and insertions take O(1) on average, the overall time complexity is dominated by the maximum number of division steps before a repeating remainder is found or the remainder becomes zero, leading to O(n) time complexity.

Space Complexity

O(N) – The algorithm uses a hash map (or dictionary) to store remainders encountered during the long division process, along with their corresponding positions. In the worst-case scenario, where the decimal representation is non-repeating or has a very long repeating cycle, the hash map could potentially store all remainders up to the value of the denominator. Therefore, the space used by the hash map grows linearly with the magnitude of the denominator (let's denote the magnitude as N), as we store each unique remainder and its index. Hence, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Numerator is zero	Return '0' immediately to avoid division by zero errors or unnecessary calculations.
Denominator is zero	Throw an IllegalArgumentException (or similar) as division by zero is undefined.
Integer overflow during multiplication/division	Use long data type for intermediate calculations (numerator and remainder) to avoid overflow issues.
Negative numerator and/or denominator	Handle signs separately and append the correct sign to the result.
Non-terminating repeating decimal with a very long cycle	The map storing remainders and their indices should dynamically grow to accommodate long cycles, and StringBuilder's capacity should be sufficient.
Input is MAX_INT or MIN_INT	Cast inputs to long immediately to avoid Integer.MIN_VALUE / -1 issues.
Result is a whole number (no decimal part)	The algorithm should correctly identify that there is no fractional part and return the integer part only.
Both numerator and denominator are MAX_INT or MIN_INT	Handle the sign and then perform the long division to avoid unexpected results.

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:

Can the numerator and denominator be negative or zero?
What is the expected output if the decimal representation is a non-recurring decimal (i.e., it terminates)? Should I still format it as a string?
What is the maximum possible value for the numerator and denominator, and should I be concerned about integer overflow during calculations?
If the denominator is zero, should I throw an exception or return a specific error string/value?
Are there any specific formatting requirements for the repeating decimal portion (e.g., using parentheses)? If so, what should be returned if the repeating portion has leading zeros?

Brute Force Solution

Approach

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

Start by performing long division of the numerator by the denominator.
Calculate the whole number part of the division.
If the numerator is now zero, then the decimal representation terminates and we're done.
If the numerator is not zero, start tracking the remainders we get at each step.
Multiply the remainder by 10 (as you would in long division) and perform the division again to get the next decimal digit.
Check if the new remainder we calculated already exists in our list of tracked remainders.
If the remainder is in the list, this means we've found a repeating part. The decimal representation between the first occurrence of the remainder and its second occurrence is the repeating part.
If the remainder is NOT in the list, then add it to our list and continue the division process by going back to multiplying the remainder by 10.
Keep doing the long division and tracking the remainders until either the remainder becomes zero (the decimal terminates) or you find a repeating remainder (the decimal repeats).

Code Implementation

def fraction_to_recurring_decimal(numerator, denominator):
    if numerator == 0:
        return "0"

    sign = "-" if (numerator < 0) ^ (denominator < 0) else ""
    numerator = abs(numerator)
    denominator = abs(denominator)

    whole_number_part = numerator // denominator
    remainder = numerator % denominator

    if remainder == 0:
        return sign + str(whole_number_part)

    decimal_part = ""
    remainders_seen = {}

    while remainder != 0 and remainder not in remainders_seen:
        # Store the current remainder and its index in decimal_part
        remainders_seen[remainder] = len(decimal_part)

        remainder *= 10
        decimal_part += str(remainder // denominator)
        remainder %= denominator

    if remainder == 0:
        return sign + str(whole_number_part) + "." + decimal_part
    else:
        # Repeating part found; insert parentheses
        insert_position = remainders_seen[remainder]
        decimal_part = decimal_part[:insert_position] + "(" + 
                       decimal_part[insert_position:] + ")"

        return sign + str(whole_number_part) + "." + decimal_part

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, handle the sign of the result. If either the numerator or denominator is negative (but not both), the result is negative.
Convert both the numerator and denominator to positive values to simplify the division process.
Calculate the integer part of the decimal by performing integer division.
Find the remainder after the integer division.
If the remainder is zero, the fraction results in a whole number; we're done.
If the remainder is not zero, start building the decimal part.
Use a map (or dictionary) to store remainders we've already seen, along with the position (index) where we saw them.
In a loop, multiply the remainder by 10 and perform integer division again. This gives the next digit of the decimal.
Check if the new remainder is already in the map. If it is, this indicates the start of the repeating part of the decimal. Insert parentheses around the repeating part.
If the remainder is not in the map, store it along with its current position and continue the loop.
If the remainder becomes zero, the decimal terminates, and we're done.
Return the result, which consists of the integer part, a decimal point, the non-repeating part of the decimal, and the repeating part (if any) enclosed in parentheses.

Code Implementation

def fraction_to_recurring_decimal(numerator, denominator):
    if numerator == 0:
        return "0"

    sign = "-" if (numerator < 0) ^ (denominator < 0) else ""
    numerator = abs(numerator)
    denominator = abs(denominator)

    integer_part = numerator // denominator
    remainder = numerator % denominator

    if remainder == 0:
        return sign + str(integer_part)

    decimal_part = ""
    remainder_map = {}

    while remainder != 0:
        # If the remainder repeats, we have found the repeating part
        if remainder in remainder_map:
            index = remainder_map[remainder]
            decimal_part = decimal_part[:index] + "(" + decimal_part[index:] + ")"
            break

        remainder_map[remainder] = len(decimal_part)
        remainder *= 10
        decimal_part += str(remainder // denominator)
        remainder %= denominator

    return sign + str(integer_part) + "." + decimal_part

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Numerator is zero	Return '0' immediately to avoid division by zero errors or unnecessary calculations.
Denominator is zero	Throw an IllegalArgumentException (or similar) as division by zero is undefined.
Integer overflow during multiplication/division	Use long data type for intermediate calculations (numerator and remainder) to avoid overflow issues.
Negative numerator and/or denominator	Handle signs separately and append the correct sign to the result.
Non-terminating repeating decimal with a very long cycle	The map storing remainders and their indices should dynamically grow to accommodate long cycles, and StringBuilder's capacity should be sufficient.
Input is MAX_INT or MIN_INT	Cast inputs to long immediately to avoid Integer.MIN_VALUE / -1 issues.
Result is a whole number (no decimal part)	The algorithm should correctly identify that there is no fractional part and return the integer part only.
Both numerator and denominator are MAX_INT or MIN_INT	Handle the sign and then perform the long division to avoid unexpected results.