Fraction to Recurring Decimal solution and explanation
Google
9 more videos on this problem
Fraction to Recurring Decimal (Leetcode 166) Solution | Hashmap Interview Question PlaylistPepcoding · 35:03 · 24K views
LeetCode 166. Fraction to Recurring Decimal Explanation and Solutionhappygirlzt · 6:48 · 16K views
166. Fraction to Recurring Decimal Leetcode SolutionCode Crusaders · 4:36 · 3K views
166. Fraction to Recurring Decimal | Leetcode Daily - PythonLeetcode Daily · 4:45 · 2K views
166. Fraction to Recurring Decimal - English VersionSimple Code - 단순코드 · 9:29 · 1K views
LeetCode 166. Fraction to Recurring Decimal Solution Explained - JavaAlgorithms and Data Structures Course · 13:25 · 1K views
Fraction to Recurring Decimal - LeetCode 166 - GolangLast Programmer · 15:59 · 681 views
LeetCode 166 | Fraction to recurring DecimalCode Harmony · 23:22 · 519 views
166 Fraction to Recurring Decimal | LeetCodeR Sai Siddhu · 10:00 · 516 views
LeetCode 166 🔥 Fraction to Recurring Decimal | Daily Challenge | Optimal Java Solution + Dry Run Study Placement · 13:45 · 273 views
The 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.
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 != 0
Approach overview
Problem Overview: You receive two integers representing a fraction: numerator / denominator. The task is to return the decimal representation as a string. If the fractional part repeats, enclose the repeating sequence in parentheses. For example, 1/3 becomes "0.(3)" and 2/4 becomes "0.5".
Approach 1: Basic Long Division Simulation (O(n^2) time, O(1) space)
The most direct idea is to simulate manual long division. Divide the numerator by the denominator to get the integer part, then repeatedly multiply the remainder by 10 and divide again to produce decimal digits. The challenge is detecting when digits start repeating. Without storing previously seen remainders, you must repeatedly scan the built string to detect cycles, which can degrade performance. This approach demonstrates the mechanics of long division but becomes inefficient as the repeating sequence grows.
Approach 2: Long Division with Remainder Tracking (O(n) time, O(n) space)
The optimal solution simulates long division but tracks each remainder in a hash table. Each remainder maps to the index in the output string where its digit first appeared. When the same remainder appears again, the digits between those indices form a repeating cycle. Insert an opening parenthesis at the first occurrence and append a closing parenthesis at the end. Handle sign separately and work with absolute values to avoid overflow. The algorithm repeatedly multiplies the remainder by 10, appends remainder / denominator to the result, and updates the remainder with remainder % denominator. Since each unique remainder is processed once, the runtime is O(n) where n is bounded by the denominator.
This method relies on properties of division from math and uses a string builder to construct the result efficiently. The key insight: repeating decimals occur when the same remainder reappears during long division.
Recommended for interviews: Interviewers expect the long division with remainder tracking solution. The brute simulation shows you understand how decimal expansion works, but the hash map optimization demonstrates algorithmic thinking and knowledge of cycle detection. The optimal approach runs in O(n) time with O(n) extra space and cleanly handles both terminating and repeating decimals.
Approach 1: Long Division with Remainder Tracking
This method utilizes long division to compute the fraction part. We keep track of the remainder at each step using a hash map (or dictionary), which maps the remainder to its corresponding position in the decimal.
If a remainder repeats, it means the decimals will start repeating onwards, and we enclose the repeating sequence in parentheses.
def fractionToDecimal(numerator, denominator):
if numerator == 0:
return "0"
result = []
if (numerator < 0) ^ (denominator < 0):
result.append("-")
numerator, denominator = abs(numerator), abs(denominator)
result.append(str(numerator // denominator))
remainder = numerator % denominator
if remainder == 0:
return ''.join(result)
result.append(".")
position_map = {}
while remainder:
if remainder in position_map:
result.insert(position_map[remainder], "(")
result.append(")")
break
position_map[remainder] = len(result)
remainder *= 10
result.append(str(remainder // denominator))
remainder %= denominator
return ''.join(result)import java.util.HashMap;
public 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 den = Math.abs((long) denominator);
result.append(num / den);
long remainder = num % den;
if (remainder == 0) return result.toString();
result.append(".");
HashMap<Long, Integer> 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 / den);
remainder %= den;
}
return result.toString();
}
}#include <string>
#include <unordered_map>
class Solution {
public:
std::string fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
std::string result;
if ((numerator < 0) ^ (denominator < 0)) result += "-";
long num = std::labs(numerator);
long den = std::labs(denominator);
result += std::to_string(num / den);
long remainder = num % den;
if (remainder == 0) return result;
result += ".";
std::unordered_map<long, int> map;
while (remainder) {
if (map.find(remainder) != map.end()) {
result.insert(map[remainder], "(");
result += ")";
break;
}
map[remainder] = result.size();
remainder *= 10;
result += std::to_string(remainder / den);
remainder %= den;
}
return result;
}
};var fractionToDecimal = function(numerator, denominator) {
if (numerator === 0) return "0";
let result = '';
if (numerator < 0 ^ denominator < 0) result += '-';
let num = Math.abs(numerator);
let den = Math.abs(denominator);
result += Math.floor(num / den);
let remainder = num % den;
if (remainder === 0) return result;
result += '.';
const map = new Map();
while (remainder !== 0) {
if (map.has(remainder)) {
const pos = map.get(remainder);
result = result.slice(0, pos) + '(' + result.slice(pos) + ')';
break;
}
map.set(remainder, result.length);
remainder *= 10;
result += Math.floor(remainder / den);
remainder %= den;
}
return result;
};#include <string.h>
#include <stdio.h>
#include <stdlib.h>
char* fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
char* result = malloc(10000);
int index = 0;
if ((numerator < 0) ^ (denominator < 0)) {
result[index++] = '-';
}
// Convert to long long to avoid overflow
long long num = llabs(numerator);
long long den = llabs(denominator);
index += sprintf(result+index, "%lld", num / den);
long long remainder = num % den;
if (remainder == 0) {
result[index] = '\0';
return result;
}
result[index++] = '.';
int* map = calloc(den, sizeof(int));
memset(map, -1, den * sizeof(int));
while (remainder != 0) {
if (map[remainder] != -1) {
int pos = map[remainder];
memmove(result + pos + 1, result + pos, index - pos);
result[pos] = '(';
result[index + 1] = ')';
result[index + 2] = '\0';
free(map);
return result;
}
map[remainder] = index;
remainder *= 10;
index += sprintf(result+index, "%lld", remainder / den);
remainder %= den;
}
result[index] = '\0';
free(map);
return result;
}using System;
using System.Text;
using System.Collections.Generic;
public 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 den = Math.Abs((long)denominator);
result.Append(num / den);
long remainder = num % den;
if (remainder == 0) return result.ToString();
result.Append('.');
Dictionary<long, int> map = new Dictionary<long, int>();
while (remainder != 0) {
if (map.ContainsKey(remainder)) {
result.Insert(map[remainder], "(");
result.Append(')');
break;
}
map[remainder] = result.Length;
remainder *= 10;
result.Append(remainder / den);
remainder %= den;
}
return result.ToString();
}
}The code starts by checking if the numerator is zero, in which case '0' is returned since no fraction can be formed. Then, it determines the sign of the result by checking if the numerator and denominator have opposite signs.
The result list is used to build the final string. Initially, we append the integral part of the division. If there's no remainder after this division, the process stops.
If there is a remainder, we enter a loop to handle the fractional part of the division. A map keeps track of the positions of previously seen remainders. If a remainder repeats, it indicates the start of a repeating sequence and parentheses are added around the sequence.
Time Complexity: O(d), where d is the length of the repeating sequence in the worst case. This is because each fractional digit is calculated one at a time.
Space Complexity: O(d), for storing seen remainders in the hash map.
Approach 2: Mathematics + Hash Table
First, we check if the numerator is 0. If it is, we return "0" directly.
Next, we check if the numerator and denominator have different signs. If they do, the result is negative, and we set the first character of the result to "-".
Then we take the absolute values of the numerator and denominator, denoted as a and b. Since the range of the numerator and denominator is [-2^{31}, 2^{31} - 1], taking the absolute value directly may cause overflow, so we convert both a and b to long integers.
Next, we calculate the integer part, which is the integer part of a divided by b, convert it to a string, and add it to the result. Then we take the remainder of a divided by b, denoted as a.
If a is 0, it means the result is an integer, and we return the result directly.
Next, we calculate the decimal part. We use a hash table d to record the length of the result corresponding to each remainder. We continuously multiply a by 10, then add the integer part of a divided by b to the result, then take the remainder of a divided by b, denoted as a. If a is 0, it means the result is a finite decimal, and we return the result directly. If a has appeared in the hash table, it means the result is a recurring decimal. We find the starting position of the cycle, insert the result into parentheses, and then return the result.
The time complexity is O(l), and the space complexity is O(l), where l is the length of the result. In this problem, l < 10^4.
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('');
}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
}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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Long Division with Remainder Tracking | Time Complexity: O(d), where d is the length of the repeating sequence in the worst case. This is because each fractional digit is calculated one at a time. Space Complexity: O(d), for storing seen remainders in the hash map. |
| Mathematics + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Basic Long Division Simulation | O(n^2) | O(1) | Educational understanding of decimal expansion without extra memory |
| Long Division with Remainder Hash Map | O(n) | O(n) | General case; efficiently detects repeating decimals during division |
Frequently asked questions
Is Fraction to Recurring Decimal easy or hard?
Fraction to Recurring Decimal is generally considered a medium difficulty problem. The arithmetic itself is simple, but correctly detecting repeating cycles, handling negative numbers, and avoiding overflow requires careful implementation.
Fraction to Recurring Decimal Python/Java solution
Most implementations follow the same logic: determine the sign, compute the integer part, and simulate long division for the fractional part. A hash map tracks remainders and their positions. The code structure is nearly identical across Python, Java, C++, C#, and JavaScript.
How to solve Fraction to Recurring Decimal in O(n)?
Perform long division and keep a hash map that records the index where each remainder first appeared in the result string. Multiply the remainder by 10 each step, append the digit from division, and update the remainder. If a remainder repeats, insert parentheses around the repeating substring.
What is the best approach for Fraction to Recurring Decimal?
The standard solution simulates long division while storing each remainder in a hash map. When a remainder repeats, the digits between the two occurrences form the repeating cycle. This approach runs in O(n) time and O(n) space, where n is the number of digits produced in the decimal expansion.
Is Fraction to Recurring Decimal asked at Google/Amazon/Meta?
Fraction to Recurring Decimal is a classic string and math interview problem that appears in technical interviews at large tech companies. Variants of the problem are reported in interviews at companies like Google, Amazon, and Meta because it tests simulation, hash maps, and edge case handling.
What data structure is used in Fraction to Recurring Decimal?
A hash table (hash map) is used to map each remainder to the index where its corresponding digit was added in the result string. This allows constant-time detection of repeating remainders, which indicates the start of a recurring decimal cycle.
What is the time complexity of Fraction to Recurring Decimal?
The optimal algorithm runs in O(n) time because each unique remainder appears at most once during long division. Since the number of possible remainders is bounded by the denominator, the loop terminates after at most n steps. Space complexity is also O(n) due to the hash map storing remainders and their positions.