Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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.
Note that if the fraction can be represented as a finite length string, you must return it.
Example 1:
Input: numerator = 1, denominator = 2 Output: "0.5"
Example 2:
Input: numerator = 2, denominator = 1 Output: "2"
Example 3:
Input: numerator = 4, denominator = 333 Output: "0.(012)"
Constraints:
-231 <= numerator, denominator <= 231 - 1denominator != 0Problem summary: 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. Note that if the fraction can be represented as a finite length string, you must return it.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Math
1 2
2 1
4 333
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #166: Fraction to Recurring Decimal
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
boolean neg = (numerator > 0) ^ (denominator > 0);
sb.append(neg ? "-" : "");
long a = Math.abs((long) numerator), b = Math.abs((long) denominator);
sb.append(a / b);
a %= b;
if (a == 0) {
return sb.toString();
}
sb.append(".");
Map<Long, Integer> d = new HashMap<>();
while (a != 0) {
d.put(a, sb.length());
a *= 10;
sb.append(a / b);
a %= b;
if (d.containsKey(a)) {
sb.insert(d.get(a), "(");
sb.append(")");
break;
}
}
return sb.toString();
}
}
// Accepted solution for LeetCode #166: Fraction to Recurring Decimal
func fractionToDecimal(numerator int, denominator int) string {
if numerator == 0 {
return "0"
}
ans := ""
if (numerator > 0) != (denominator > 0) {
ans += "-"
}
a := int64(numerator)
b := int64(denominator)
a = abs(a)
b = abs(b)
ans += strconv.FormatInt(a/b, 10)
a %= b
if a == 0 {
return ans
}
ans += "."
d := make(map[int64]int)
for a != 0 {
if pos, ok := d[a]; ok {
ans = ans[:pos] + "(" + ans[pos:] + ")"
break
}
d[a] = len(ans)
a *= 10
ans += strconv.FormatInt(a/b, 10)
a %= b
}
return ans
}
func abs(x int64) int64 {
if x < 0 {
return -x
}
return x
}
# Accepted solution for LeetCode #166: Fraction to Recurring Decimal
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
if numerator == 0:
return "0"
ans = []
neg = (numerator > 0) ^ (denominator > 0)
if neg:
ans.append("-")
a, b = abs(numerator), abs(denominator)
ans.append(str(a // b))
a %= b
if a == 0:
return "".join(ans)
ans.append(".")
d = {}
while a:
d[a] = len(ans)
a *= 10
ans.append(str(a // b))
a %= b
if a in d:
ans.insert(d[a], "(")
ans.append(")")
break
return "".join(ans)
// Accepted solution for LeetCode #166: Fraction to Recurring Decimal
use std::collections::HashMap;
impl Solution {
pub fn fraction_to_decimal(numerator: i32, denominator: i32) -> String {
if numerator == 0 {
return "0".to_string();
}
let mut ans = String::new();
let neg = (numerator > 0) ^ (denominator > 0);
if neg {
ans.push('-');
}
let mut a = (numerator as i64).abs();
let b = (denominator as i64).abs();
ans.push_str(&(a / b).to_string());
a %= b;
if a == 0 {
return ans;
}
ans.push('.');
let mut d: HashMap<i64, usize> = HashMap::new();
while a != 0 {
if let Some(&pos) = d.get(&a) {
ans.insert(pos, '(');
ans.push(')');
break;
}
d.insert(a, ans.len());
a *= 10;
ans.push_str(&(a / b).to_string());
a %= b;
}
ans
}
}
// Accepted solution for LeetCode #166: Fraction to Recurring Decimal
function fractionToDecimal(numerator: number, denominator: number): string {
if (numerator === 0) {
return '0';
}
const sb: string[] = [];
const neg: boolean = numerator > 0 !== denominator > 0;
sb.push(neg ? '-' : '');
let a: number = Math.abs(numerator),
b: number = Math.abs(denominator);
sb.push(Math.floor(a / b).toString());
a %= b;
if (a === 0) {
return sb.join('');
}
sb.push('.');
const d: Map<number, number> = new Map();
while (a !== 0) {
d.set(a, sb.length);
a *= 10;
sb.push(Math.floor(a / b).toString());
a %= b;
if (d.has(a)) {
sb.splice(d.get(a)!, 0, '(');
sb.push(')');
break;
}
}
return sb.join('');
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.