Fraction to recurring decimal

XXX. Fraction to Recurring Decimal

Math

Hash Map

Problem Statement:

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.

Algorithm:

1. Handle edge cases involving signs by determining the sign of the result based on the numerator and denominator.
2. Perform long division to calculate the integral part of the fraction.
3. If there is a remainder, append a decimal point and use a hash map to track remainders:
   • For every new remainder, store its position in the result string.
   • If the remainder repeats, identify the repeating part and enclose it in parentheses.

Complexity:

Time Complexity: O(d), where d is the size of the denominator. This is because the remainder will repeat after at most d steps.
Space Complexity: O(d) for the hash map used to track remainders.

Java Implementation:

class Solution {
    // Very simple long division, you just gotta know long division
    // Trick is repeating part just put the remainder in a hashmap mapped to the first occurrence
    public String fractionToDecimal(int numerator, int denominator) {
        StringBuilder result = new StringBuilder();
        String sign = (numerator < 0 == denominator < 0 || numerator == 0) ? "" : "-";

        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);

        result.append(sign);
        result.append(num / den);
        long rem = num % den;
        if (rem == 0) return result.toString();

        result.append(".");
        Map map = new HashMap<>(); // store numerator as repetition of same numerator will cause recurring
        while(rem != 0) {
            if (!map.containsKey(rem)) {
                map.put(rem, result.length()); // for a given numerator its (num*10)/den starts from this idx
            } else {
                int idx = map.get(rem);
                return result.substring(0, idx) + "(" + result.substring(idx) + ")";
            }

            rem *= 10;

            result.append(rem / den);
            rem = rem - den * (rem / den); // Same as rem = rem % den
        }
        return result.toString();
    }
}
                

Python Implementation:

def fraction_to_decimal(numerator, denominator):
    sign = "" if (numerator < 0) == (denominator < 0) or numerator == 0 else "-"

    num, den = abs(numerator), abs(denominator)
    result = [sign + str(num // den)]
    rem = num % den
    if rem == 0:
        return "".join(result)

    result.append(".")
    rem_map = {}

    while rem != 0:
        if rem in rem_map:
            idx = rem_map[rem]
            result.insert(idx, "(")
            result.append(")")
            break

        rem_map[rem] = len(result)
        rem *= 10
        result.append(str(rem // den))
        rem %= den

    return "".join(result)
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

string fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) return "0";

    string sign = (numerator < 0) == (denominator < 0) ? "" : "-";
    long num = abs((long)numerator);
    long den = abs((long)denominator);

    string result = sign + to_string(num / den);
    long rem = num % den;
    if (rem == 0) return result;

    result += ".";
    unordered_map rem_map;

    while (rem != 0) {
        if (rem_map.find(rem) != rem_map.end()) {
            result.insert(rem_map[rem], "(");
            result += ")";
            break;
        }

        rem_map[rem] = result.size();
        rem *= 10;
        result += to_string(rem / den);
        rem %= den;
    }

    return result;
}