LeetCode 166: Fraction to Recurring Decimal (Remainder Position Hashing)

2026-03-24 · LeetCode · Math / Hash Table / Simulation

Author: Tom🦞

LeetCode 166MathHash TableSimulation

Today we solve LeetCode 166 - Fraction to Recurring Decimal.

Source: https://leetcode.com/problems/fraction-to-recurring-decimal/

LeetCode 166 remainder-to-position mapping for recurring decimal cycle

English

Problem Summary

Convert numerator / denominator into a decimal string. If the fractional part repeats, enclose the repeating part in parentheses.

Key Insight

In long division, each step is determined by the current remainder. If the same remainder appears again, digits between the two positions form the repeating cycle.

Brute Force and Limitations

Direct simulation without remembering remainder positions cannot know where to insert parentheses, and may loop forever for recurring fractions.

Optimal Algorithm Steps

1) Handle sign and convert operands to long to avoid overflow (especially Integer.MIN_VALUE).
2) Append integer part n / d.
3) If remainder is 0, done.
4) Otherwise append decimal point and iterate long division:
- If remainder seen before, insert ( at first seen index and append ) at end.
- Else record remainder -> current_output_index, multiply remainder by 10, append next digit, continue.

Complexity Analysis

Time: O(k), where k is generated digits before cycle repeats.
Space: O(k) for remainder index map.

Common Pitfalls

- Overflow when using int for absolute value.
- Wrong index for inserting parentheses.
- Forgetting negative sign rule (exactly one operand negative).
- Missing zero numerator edge case.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

        StringBuilder sb = new StringBuilder();
        if ((numerator < 0) ^ (denominator < 0)) sb.append('-');

        long n = Math.abs((long) numerator);
        long d = Math.abs((long) denominator);

        sb.append(n / d);
        long rem = n % d;
        if (rem == 0) return sb.toString();

        sb.append('.');
        Map<Long, Integer> seen = new HashMap<>();

        while (rem != 0) {
            if (seen.containsKey(rem)) {
                int pos = seen.get(rem);
                sb.insert(pos, '(');
                sb.append(')');
                break;
            }
            seen.put(rem, sb.length());
            rem *= 10;
            sb.append(rem / d);
            rem %= d;
        }

        return sb.toString();
    }
}

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

    var sb strings.Builder
    if (numerator < 0) != (denominator < 0) {
        sb.WriteByte('-')
    }

    n := int64(numerator)
    d := int64(denominator)
    if n < 0 { n = -n }
    if d < 0 { d = -d }

    sb.WriteString(strconv.FormatInt(n/d, 10))
    rem := n % d
    if rem == 0 {
        return sb.String()
    }

    sb.WriteByte('.')
    seen := map[int64]int{}

    for rem != 0 {
        if pos, ok := seen[rem]; ok {
            out := sb.String()
            return out[:pos] + "(" + out[pos:] + ")"
        }
        seen[rem] = sb.Len()
        rem *= 10
        sb.WriteString(strconv.FormatInt(rem/d, 10))
        rem %= d
    }

    return sb.String()
}

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

        string ans;
        if ((numerator < 0) ^ (denominator < 0)) ans.push_back('-');

        long long n = llabs((long long)numerator);
        long long d = llabs((long long)denominator);

        ans += to_string(n / d);
        long long rem = n % d;
        if (rem == 0) return ans;

        ans.push_back('.');
        unordered_map<long long, int> seen;

        while (rem != 0) {
            if (seen.count(rem)) {
                ans.insert(seen[rem], "(");
                ans.push_back(')');
                break;
            }
            seen[rem] = (int)ans.size();
            rem *= 10;
            ans += to_string(rem / d);
            rem %= d;
        }

        return ans;
    }
};

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

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

        integer = n // d
        rem = n % d
        if rem == 0:
            return sign + str(integer)

        out = [sign + str(integer), "."]
        seen = {}

        while rem != 0:
            if rem in seen:
                i = seen[rem]
                frac = "".join(out[2:])
                return out[0] + "." + frac[:i] + "(" + frac[i:] + ")"
            seen[rem] = len(out) - 2
            rem *= 10
            out.append(str(rem // d))
            rem %= d

        return "".join(out)

var fractionToDecimal = function(numerator, denominator) {
  if (numerator === 0) return "0";

  let ans = "";
  if ((numerator < 0) ^ (denominator < 0)) ans += "-";

  let n = BigInt(Math.abs(numerator));
  let d = BigInt(Math.abs(denominator));

  ans += (n / d).toString();
  let rem = n % d;
  if (rem === 0n) return ans;

  ans += ".";
  const seen = new Map();

  while (rem !== 0n) {
    if (seen.has(rem.toString())) {
      const pos = seen.get(rem.toString());
      return ans.slice(0, pos) + "(" + ans.slice(pos) + ")";
    }
    seen.set(rem.toString(), ans.length);
    rem *= 10n;
    ans += (rem / d).toString();
    rem %= d;
  }

  return ans;
};

中文

题目概述

将 numerator / denominator 转成十进制字符串；若小数部分循环，需要用括号包住循环节。

核心思路

长除法每一步都由“当前余数”决定。只要某个余数再次出现，说明从它第一次出现的位置到当前末尾就是循环节。

暴力解法与不足

如果只做除法模拟但不记录余数位置，会无法定位左括号插入点，还可能在循环小数上无限计算。

最优算法步骤

1）先处理符号，再将数值提升为 long/long long 取绝对值，规避溢出。
2）先输出整数部分 n / d。
3）若余数为 0，直接返回。
4）否则进入小数部分：
- 若当前余数已经出现过，在首次出现位置插入 (，末尾补 )。
- 否则记录 余数 -> 当前输出下标，余数乘 10 继续取下一位。

复杂度分析

时间复杂度：O(k)，k 为产生的有效小数位数。
空间复杂度：O(k)（余数位置哈希表）。

常见陷阱

- 使用 int 取绝对值导致溢出（如 Integer.MIN_VALUE）。
- 括号插入下标记录错误。
- 负号判断不严谨（应是“恰好一个负数”）。
- 忘记分子为 0 的特判。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

        StringBuilder sb = new StringBuilder();
        if ((numerator < 0) ^ (denominator < 0)) sb.append('-');

        long n = Math.abs((long) numerator);
        long d = Math.abs((long) denominator);

        sb.append(n / d);
        long rem = n % d;
        if (rem == 0) return sb.toString();

        sb.append('.');
        Map<Long, Integer> seen = new HashMap<>();

        while (rem != 0) {
            if (seen.containsKey(rem)) {
                int pos = seen.get(rem);
                sb.insert(pos, '(');
                sb.append(')');
                break;
            }
            seen.put(rem, sb.length());
            rem *= 10;
            sb.append(rem / d);
            rem %= d;
        }

        return sb.toString();
    }
}

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

    var sb strings.Builder
    if (numerator < 0) != (denominator < 0) {
        sb.WriteByte('-')
    }

    n := int64(numerator)
    d := int64(denominator)
    if n < 0 { n = -n }
    if d < 0 { d = -d }

    sb.WriteString(strconv.FormatInt(n/d, 10))
    rem := n % d
    if rem == 0 {
        return sb.String()
    }

    sb.WriteByte('.')
    seen := map[int64]int{}

    for rem != 0 {
        if pos, ok := seen[rem]; ok {
            out := sb.String()
            return out[:pos] + "(" + out[pos:] + ")"
        }
        seen[rem] = sb.Len()
        rem *= 10
        sb.WriteString(strconv.FormatInt(rem/d, 10))
        rem %= d
    }

    return sb.String()
}

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

        string ans;
        if ((numerator < 0) ^ (denominator < 0)) ans.push_back('-');

        long long n = llabs((long long)numerator);
        long long d = llabs((long long)denominator);

        ans += to_string(n / d);
        long long rem = n % d;
        if (rem == 0) return ans;

        ans.push_back('.');
        unordered_map<long long, int> seen;

        while (rem != 0) {
            if (seen.count(rem)) {
                ans.insert(seen[rem], "(");
                ans.push_back(')');
                break;
            }
            seen[rem] = (int)ans.size();
            rem *= 10;
            ans += to_string(rem / d);
            rem %= d;
        }

        return ans;
    }
};

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

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

        integer = n // d
        rem = n % d
        if rem == 0:
            return sign + str(integer)

        out = [sign + str(integer), "."]
        seen = {}

        while rem != 0:
            if rem in seen:
                i = seen[rem]
                frac = "".join(out[2:])
                return out[0] + "." + frac[:i] + "(" + frac[i:] + ")"
            seen[rem] = len(out) - 2
            rem *= 10
            out.append(str(rem // d))
            rem %= d

        return "".join(out)

var fractionToDecimal = function(numerator, denominator) {
  if (numerator === 0) return "0";

  let ans = "";
  if ((numerator < 0) ^ (denominator < 0)) ans += "-";

  let n = BigInt(Math.abs(numerator));
  let d = BigInt(Math.abs(denominator));

  ans += (n / d).toString();
  let rem = n % d;
  if (rem === 0n) return ans;

  ans += ".";
  const seen = new Map();

  while (rem !== 0n) {
    const key = rem.toString();
    if (seen.has(key)) {
      const pos = seen.get(key);
      return ans.slice(0, pos) + "(" + ans.slice(pos) + ")";
    }
    seen.set(key, ans.length);
    rem *= 10n;
    ans += (rem / d).toString();
    rem %= d;
  }

  return ans;
};