166. Fraction to Recurring Decimal

Description

The problem is to convert a fraction, given as a numerator and a denominator, into its decimal representation as a string. If the decimal representation has a repeating sequence, it should be enclosed in parentheses. For example, the fraction 1/3 should be represented as "0.(3)", and the fraction 2/1 as "2". The function should handle both positive and negative values and return the correct string representation for each case.

Intuition

The challenge in converting a fraction to its decimal form lies in detecting repeating sequences. When dividing the numerator by the denominator, if the remainder repeats at any point, the sequence of digits between those repeated remainders is the repeating part of the decimal. By tracking the position of each remainder, we can determine when the digits start repeating.

Approach

1. Handle Sign and Initial Division: - Determine if the result should be negative by checking the signs of the numerator and denominator. - Compute the integer part of the division and append it to the result string. - If there is no remainder after the initial division, return the result as is.
2. Detect Repeating Sequence: - Use a map (or dictionary) to track the position of each remainder during the division process. - Multiply the remainder by 10, divide by the denominator, and append the result to the decimal part of the result string. - If a remainder repeats (i.e., it appears in the map), the digits between its first appearance and the current position form a repeating sequence. Insert parentheses around this sequence.
3. Return the Result: - If no repeating sequence is detected, return the decimal result as is. - If a repeating sequence is detected, return the result with the repeating part enclosed in parentheses.

Complexity

Time Complexity:

O(n), where n is the length of the decimal representation before a repeating sequence (if any). In the worst case, this could be as long as the denominator.

Space Complexity:

O(n), where n is the number of unique remainders that may need to be tracked to detect a repeating sequence. This could also be as large as the denominator.

Code

C++

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        
        string result;
        if ((numerator < 0) ^ (denominator < 0)) {
            result += "-";
        }

        long long num = abs((long long)numerator);
        long long denom = abs((long long)denominator);
        long long remainder = num % denom;

        result += to_string(num / denom);

        if (remainder == 0) {
            return result;
        }

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

            map[remainder] = result.size();

            remainder *= 10;
            result += to_string(remainder / denom);
            remainder %= denom;
        }

        return result;
    }
};

Python

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"

        result = []
        if (numerator < 0) ^ (denominator < 0):
            result.append("-")

        num = abs(numerator)
        denom = abs(denominator)
        remainder = num % denom

        result.append(str(num // denom))

        if remainder == 0:
            return "".join(result)

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

        while remainder != 0:
            if remainder in remainder_map:
                result.insert(remainder_map[remainder], "(")
                result.append(")")
                break

            remainder_map[remainder] = len(result)

            remainder *= 10
            result.append(str(remainder // denom))
            remainder %= denom

        return "".join(result)

Java

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";

        StringBuilder result = new StringBuilder();
        if (numerator < 0 ^ denominator < 0) {
            result.append("-");
        }

        long num = Math.abs((long) numerator);
        long denom = Math.abs((long) denominator);
        long remainder = num % denom;

        result.append(num / denom);

        if (remainder == 0) {
            return result.toString();
        }

        result.append(".");
        HashMap map = new HashMap<>();

        while (remainder != 0) {
            if (map.containsKey(remainder)) {
                result.insert(map.get(remainder), "(");
                result.append(")");
                break;
            }

            map.put(remainder, result.length());

            remainder *= 10;
            result.append(remainder / denom);
            remainder %= denom;
        }

        return result.toString();
    }
}

JavaScript

var fractionToDecimal = function(numerator, denominator) {

    if (numerator === 0) return "0";

    var map = new Map();
    var result = "";

    if (Math.sign(numerator) !== Math.sign(denominator)) {
        result += "-";
    }
    const posNumr = Math.abs(numerator);
    const posDenom = Math.abs(denominator);
    var remainder = posNumr % posDenom;
    result += Math.floor(posNumr/posDenom)


    if (remainder === 0) {
        return result;
    }

     result += ".";
    while(remainder !== 0) {
        if (map.has(remainder)) {
            // repeating patten detected;
            const index = map.get(remainder);
            result = result.slice(0, index) + "(" + result.slice(index) + ")";
            break;
        }

        map.set(remainder, result.length);

        remainder *= 10;
        result += Math.floor(remainder/posDenom);
        remainder %= posDenom;
    }
    
    return result;
};