Fraction to Recurring Decimal

Updated on 30 May, 2025
Fraction to Recurring Decimal header image

Problem Statement

The challenge at hand requires us to create a fraction string representation from two integers, a numerator and a denominator. The essence of the problem lies in the way the fraction is presented:

  1. If it's a simple fraction that resolves to a whole number or a terminating decimal, it should be displayed as such.
  2. For fractions that result in a repeating decimal, the periodically repeating numeral sequence must be enclosed within parentheses.

The solution needs to handle different scenarios robustly, adjusting the format based on whether the decimal is repeating or not. It is also important to highlight that large inputs are to be expected, but the size of the resulting string will not exceed 10,000 characters.

Examples

Example 1

Input:

numerator = 1
denominator = 2

Output:

"0.5"

Explanation:

1 divided by 2 is 0.5, a terminating decimal.

Example 2

Input:

numerator = 2
denominator = 1

Output:

"2"

Explanation:

2 divided by 1 is 2, a whole number.

Example 3

Input:

numerator = 4
denominator = 333

Output:

"0.(012)"

Explanation:

The decimal repeats with the sequence 012, which is enclosed in parentheses.

Constraints

  • -2^31 <= numerator, denominator <= 2^31 - 1
  • denominator != 0

Approach and Intuition

To solve the problem of converting a fraction to its string representation with proper handling of repeating decimals, follow these steps:

  1. Handle signs and whole part:

    • Determine the sign based on the inputs.
    • Take absolute values and compute the integral part using integer division.
    • If there is no remainder, return the result directly as a string.
  2. Detect and process repeating decimals:

    • For the fractional part, use long division manually.
    • Use a dictionary to map remainders to their position in the decimal string.
    • If a remainder repeats, insert parentheses at the first occurrence of that remainder.
  3. Special Cases:

    • If numerator is 0, return "0".
    • If denominator is 1 or divides the numerator completely, return a plain string integer.
    • Only add a - sign if the result is negative.

This approach uses basic arithmetic and remainder tracking to accurately capture both terminating and repeating decimal behaviors.

Solutions

  • C++
  • Java
  • JavaScript
  • Python
cpp
class Solution {
public:
    string fractionToString(int num, int denom) {
        if (num == 0) {
            return "0";
        }
        string result;
        // Check for negative result
        if (num < 0 ^ denom < 0) {
            result += "-";
        }
        // Avoid overflow issues
        long long numerator = llabs((long long)num);
        long long denominator = llabs((long long)denom);
        result += to_string(numerator / denominator);
        long long rem = numerator % denominator;
        if (rem == 0) {
            return result;
        }
        result += ".";
        unordered_map<long long, int> record;
        while (rem != 0) {
            if (record.count(rem)) {
                result.insert(record[rem], "(");
                result += ")";
                break;
            }
            record[rem] = result.length();
            rem *= 10;
            result += to_string(rem / denominator);
            rem %= denominator;
        }
        return result;
    }
};

To convert a fraction to its decimal form where the decimal might recur, you can use a C++ function that effectively handles different cases including zero, positives, and negatives, as well as repeating decimals. Here is a concise summary of how to implement this based on the provided C++ code:

  1. Start by verifying if the numerator is zero. If so, return "0" since any number divided by another (non-zero) number results in zero.

  2. Initialize a string to build your result. Check and append a "-" to the result if the fraction result is negative (i.e., if only one of either denominator or numerator is negative).

  3. Convert both the numerator and the denominator into positive values using llabs function to avoid overflow and to handle the division and modulus operations properly.

  4. Perform integer division of the absolute values of numerator and denominator to fetch the integral part of the result and append it to the result string.

  5. Calculate the remainder of the division. If the remainder is zero, return the current result as the division yields a non-recurring decimal.

  6. If the remainder is not zero, append a period ('.') to the result string signaling the beginning of the fractional part.

  7. Use a hash map to track remainders and their corresponding positions in the result string. This aids in identifying the start of recurring decimals.

  8. Multiply the remainder by 10 before dividing by the denominator again to compute the next digit of the fractional part. Continue this process and keep checking whether the current remainder has appeared before in the hash map:

    • If it has, insert an open parenthesis at the recorded position and append a close parenthesis to the end of the result to indicate the beginning and end of the recurring part.
    • Update the remainder and length of the result string accordingly until you find a repeating remainder or the remainder becomes zero.

This approach ensures that all cases are covered, including fractions that result in both recurring and non-recurring decimals. Use the hash map effectively to determine when the digits start to repeat, marking those repetitions accurately in the result string with parentheses.

java
class Solution {
    public String convertFraction(int numer, int denom) {
        if (numer == 0) {
            return "0";
        }
        StringBuilder resultText = new StringBuilder();
        if ((numer < 0) ^ (denom < 0)) {
            resultText.append("-");
        }
        long top = Math.abs(Long.valueOf(numer));
        long bottom = Math.abs(Long.valueOf(denom));
        resultText.append(String.valueOf(top / bottom));
        long rest = top % bottom;
        if (rest == 0) {
            return resultText.toString();
        }
        resultText.append(".");
        Map<Long, Integer> remainderMap = new HashMap<>();
        while (rest != 0) {
            if (remainderMap.containsKey(rest)) {
                resultText.insert(remainderMap.get(rest), "(");
                resultText.append(")");
                break;
            }
            remainderMap.put(rest, resultText.length());
            rest *= 10;
            resultText.append(String.valueOf(rest / bottom));
            rest %= bottom;
        }
        return resultText.toString();
    }
}

The Java solution provided converts a fraction represented by two integers (numerator and denominator) into its corresponding decimal format. If the decimal is repeating, it places the repeating part in parentheses. Here's a summary of how the implementation works:

  • First, it checks if the numerator is 0. If true, returns "0" since any number divided by another number (except for zero) results in 0.

  • Initializes a StringBuilder to build the resulting string. If the fraction is negative (determined by XORing the signs of the numerator and denominator), a "-" is appended to the result string.

  • Converts both the numerator and denominator into absolute values to simplify the calculation. The integer part of the division is appended to the resultText.

  • If the remainder of the division is 0, the function returns the result as it means the fraction has been simplified perfectly without any recurring decimal.

  • If there's a remainder, a decimal point is added to resultText. A HashMap is used to track the remainders and their corresponding position in the decimal sequence. This helps in identifying the beginning of the repeating sequence.

  • The remainder is then multiplied by 10, and the process is repeated: dividing by the denominator, storing the result, and checking if the remainder has appeared before.

  • If a repeating remainder is found, it inserts a "(" at the first occurrence of the remainder and appends a ")" at the end to denote the repeating sequence.

  • After completing the iterations (either through reaching zero remainder or detecting a repetition), the built string from StringBuilder is returned.

This implementation effectively addresses the conversion of fractions to their decimal representation, handling both terminating decimals and recurring decimals smartly by leveraging arithmetic operations and hashmap for memory storage.

js
var convertToDecimal = function (top, bottom) {
    if (top === 0) {
        return "0";
    }
    var result = [];
    // Add negative sign if applicable
    if ((top < 0) ^ (bottom < 0)) {
        result.push("-");
    }
    // Use absolute values to handle negatives
    var numerator = Math.abs(top);
    var denominator = Math.abs(bottom);
    result.push(Math.floor(numerator / denominator).toString());
    var rem = numerator % denominator;
    if (rem === 0) {
        return result.join("");
    }
    result.push(".");
    var positionMap = {};
    while (rem !== 0) {
        if (rem in positionMap) {
            result.splice(positionMap[rem], 0, "(");
            result.push(")");
            break;
        }
        positionMap[rem] = result.length;
        rem *= 10;
        result.push(Math.floor(rem / denominator).toString());
        rem %= denominator;
    }
    return result.join("");
};

In the JavaScript solution for converting a fraction to its decimal representation, the function convertToDecimal takes two arguments: top and bottom, representing the numerator and denominator of the fraction, respectively. This function returns a string, which is the decimal representation of the fraction, potentially as a recurring decimal enclosed in parentheses.

  • Start by checking if the numerator (top) is zero. If it is, return the string "0".
  • Initialize an empty array result to build the resulting string.
  • Check the sign of the output. If the numerator and the denominator have different signs, prepend a "-" to the result.
  • Convert both the numerator and the denominator to their absolute values to simplify the division.
  • Append the whole number part of the division to result.
  • Determine the remainder of the division. If it's zero, join and return the result as there is no fractional part.
  • If there is a remainder, append a "." to result to start the decimal fraction part.
  • Initialize a map positionMap to track positions of the remainders to detect recurring cycles.
  • Use a loop to handle the fractional part: if the remainder has been seen before (indicating a start of repetition), insert "(" at the corresponding position and append ")" at the end, then break the loop.
  • If the remainder is new, record its position in result, multiply the remainder by 10, and continue the process until the remainder becomes zero.

Return the generated string after converting the list result into a string with join(""). This function covers various edge cases like zero numerator and mixed signs, ensuring robust handling of different input values.

python
class Solution:
    def convertFractionToDecimal(self, top: int, bottom: int) -> str:
        if top == 0:
            return "0"

        result = []
        if (top < 0) != (bottom < 0):
            result.append("-")

        num = abs(top)
        denom = abs(bottom)

        result.append(str(num // denom))
        residue = num % denom
        if residue == 0:
            return "".join(result)

        result.append(".")
        positionMap = {}
        while residue != 0:
            if residue in positionMap:
                result.insert(positionMap[residue], "(")
                result.append(")")
                break

            positionMap[residue] = len(result)
            residue *= 10
            result.append(str(residue // denom))
            residue %= denom

        return "".join(result)

This article explains how to convert a fraction to its decimal representation which may be terminating or recurring. The example Python 3 implementation makes use of a Solution class containing the convertFractionToDecimal method which accepts two integer inputs: top (the numerator) and bottom (the denominator). Here are the steps followed in the code:

  1. Check if the numerator (top) is zero, since any fraction with a zero numerator will return a decimal value of "0".
  2. Initialize an empty list, result, to hold parts of the final decimal representation.
  3. Determine and append the sign of the result based on the signs of the numerator and denominator.
  4. Convert the numerator and denominator to their absolute values to simplify further operations.
  5. Append the quotient (integer part of the division) to the result list.
  6. Calculate the initial residue as the remainder of the division of the absolute values of the numerator and denominator.
  7. If the residue is zero right after computing the integer part, join and return the result as there's no fractional part.
  8. If the residue is not zero, append a decimal point to result and prepare to calculate the fractional part.
  9. Utilize a dictionary, positionMap, to store positions of residues to detect cycles indicating the start of a repeating sequence.
  10. Multiply the residue by 10 and append the result of the division to result. Continue updating the residue accordingly.
  11. If a residue repeats (found in positionMap), insert an opening parenthesis at the noted position of the first occurrence of the residue and append a closing parenthesis to denote the end of the repeating section.
  12. Finally, join all elements of the result list to form the final decimal string representation.

The key challenges addressed include handling different signs of inputs, detecting and marking the repeating parts of decimals correctly, and ensuring efficient tracking of previously seen residues to identify recurrences. This code leads to an accurate transformation of a simple fraction to its detailed decimal or repeating decimal form.

Comments

No comments yet.