Fraction to Recurring Decimal

Problem

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 104 for all the given inputs.

Examples

Example 1

1
2


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

Example 2

1
2


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

Example 3

1
2


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

Constraints

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

Solution

Method 1 – Long Division with Hash Map (Detect Cycle)

Intuition

To convert a fraction to a decimal, we perform long division. If the fractional part repeats, it means the same remainder has occurred before, so the digits between the first and second occurrence of that remainder repeat forever. We use a hash map to record the position of each remainder to detect cycles and insert parentheses around the repeating part.

Approach

Handle zero numerator (return “0”) and zero denominator (return empty string).
Determine the sign of the result.
Work with absolute values to avoid sign issues.
Compute the integer part (quotient) and append to result.
If there is no remainder, return the result.
For the fractional part, use a hash map to record the position of each remainder in the result string.
For each step:
- Multiply remainder by 10, divide by denominator to get the next digit.
- If the remainder has been seen before, insert parentheses at the first occurrence and break.
- Otherwise, record the position and continue.
Return the result string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


public String fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) return "0";
    if (denominator == 0) return "";
    StringBuilder result = new StringBuilder();
    // Handle sign
    if ((numerator < 0) ^ (denominator < 0)) result.append("-");
    long num = Math.abs((long) numerator);
    long den = Math.abs((long) denominator);
    result.append(num / den);
    long remainder = num % den;
    if (remainder == 0) return result.toString();
    result.append('.');
    Map<Long, Integer> map = new HashMap<>();
    while (remainder != 0) {
        if (map.containsKey(remainder)) {
            int idx = map.get(remainder);
            result.insert(idx, '(');
            result.append(')');
            break;
        }
        map.put(remainder, result.length());
        remainder *= 10;
        result.append(remainder / den);
        remainder %= den;
    }
    return result.toString();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if numerator == 0:
            return "0"
        if denominator == 0:
            return ""
        res = []
        if (numerator < 0) ^ (denominator < 0):
            res.append("-")
        num, den = abs(numerator), abs(denominator)
        res.append(str(num // den))
        remainder = num % den
        if remainder == 0:
            return ''.join(res)
        res.append('.')
        pos = {}
        while remainder:
            if remainder in pos:
                res.insert(pos[remainder], '(')
                res.append(')')
                break
            pos[remainder] = len(res)
            remainder *= 10
            res.append(str(remainder // den))
            remainder %= den
        return ''.join(res)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        if (denominator == 0) return "";
        string res;
        if ((numerator < 0) ^ (denominator < 0)) res += "-";
        long num = labs(numerator), den = labs(denominator);
        res += to_string(num / den);
        long remainder = num % den;
        if (remainder == 0) return res;
        res += ".";
        unordered_map<long, int> pos;
        while (remainder) {
            if (pos.count(remainder)) {
                res.insert(pos[remainder], 1, '(');
                res += ")";
                break;
            }
            pos[remainder] = res.size();
            remainder *= 10;
            res += to_string(remainder / den);
            remainder %= den;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


func fractionToDecimal(numerator int, denominator int) string {
    if numerator == 0 {
        return "0"
    }
    if denominator == 0 {
        return ""
    }
    res := ""
    if (numerator < 0) != (denominator < 0) {
        res += "-"
    }
    num, den := abs64(int64(numerator)), abs64(int64(denominator))
    res += strconv.FormatInt(num/den, 10)
    remainder := num % den
    if remainder == 0 {
        return res
    }
    res += "."
    pos := map[int64]int{}
    for remainder != 0 {
        if idx, ok := pos[remainder]; ok {
            res = res[:idx] + "(" + res[idx:] + ")"
            break
        }
        pos[remainder] = len(res)
        remainder *= 10
        res += strconv.FormatInt(remainder/den, 10)
        remainder %= den
    }
    return res
}

func abs64(x int64) int64 {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


function fractionToDecimal(numerator: number, denominator: number): string {
    if (numerator === 0) return "0";
    if (denominator === 0) return "";
    let res = '';
    if ((numerator < 0) !== (denominator < 0)) res += '-';
    let num = Math.abs(numerator), den = Math.abs(denominator);
    res += Math.floor(num / den);
    let remainder = num % den;
    if (remainder === 0) return res;
    res += '.';
    const pos = new Map<number, number>();
    while (remainder !== 0) {
        if (pos.has(remainder)) {
            const idx = pos.get(remainder)!;
            res = res.slice(0, idx) + '(' + res.slice(idx) + ')';
            break;
        }
        pos.set(remainder, res.length);
        remainder *= 10;
        res += Math.floor(remainder / den);
        remainder %= den;
    }
    return res;
}

Complexity

⏰ Time complexity: O(n), where n is the length of the repeating cycle (at most denominator). Each remainder is processed at most once.
🧺 Space complexity: O(n), for the hash map storing remainders and their positions.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Long Division with Hash Map (Detect Cycle)#

Intuition#

Approach#

Code#

Complexity#