Algorithm
Problem Name: 166. Fraction to Recurring Decimal
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
char* fractionToDecimal(int numerator, int denominator) {
char *p;
int psz, n, *dec, dsz, x;
long long num, den, k, f;
int i, repeat_at;
int neg = 0;
psz = dsz = 100; n = x = 0;
p = malloc(psz * sizeof(char));
//assert(p);
neg = ((numerator > 0 && denominator < 0) ||
(numerator < 0 && denominator > 0)) ? 1 : 0;
num = numerator;
den = denominator;
num = (num < 0) ? -num : num;
den = (den < 0) ? -den : den;
k = num / den;
f = num % den;
if (neg && (k || f)) p[n ++] = '-';
n += sprintf(&p[n], "%lld", k);
if (!f) {
p[n] = 0;
return p;
}
p[n ++] = '.';
dec = malloc(dsz * sizeof(int));
//assert(dec);
repeat_at = -1;
if (f < 0) f = -f;
while (f) {
for (i = 0; i < x; i += 2) {
if (dec[i] == f) {
repeat_at = i;
goto done;
}
}
if (x + 1 >= dsz) {
dsz *= 2;
dec = realloc(dec, dsz * sizeof(int));
//assert(dec);
}
dec[x ++] = f;
f *= 10;
k = f / den;
dec[x ++] = k;
f = f % den;
}
done:
for (i = 0; i < x; i += 2) {
if (n + 3 > psz) {
psz *= 2;
p = realloc(p, psz * sizeof(char));
//assert(p);
}
if (repeat_at == i) {
p[n ++] = '(';
}
p[n ++] = '0' + dec[i + 1];
}
if (repeat_at != -1) p[n ++] = ')';
p[n ++] = 0;
free(dec);
return p;
}
Input
numerator = 1, denominator = 2
Output
"0.5"
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) {
return "0";
}
StringBuilder fraction = new StringBuilder();
if ((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)) {
fraction.append('-');
}
long dividend = Math.abs(Long.valueOf(numerator));
long divisor = Math.abs(Long.valueOf(denominator));
fraction.append(String.valueOf(dividend / divisor));
long remainder = dividend % divisor;
if (remainder == 0) {
return fraction.toString();
}
fraction.append('.');
Map < Long, Integer> map = new HashMap<>();
while (remainder != 0) {
if (map.containsKey(remainder)) {
fraction.insert(map.get(remainder), "(");
fraction.append(')');
break;
}
map.put(remainder, fraction.length());
remainder *= 10;
fraction.append(String.valueOf(remainder / divisor));
remainder %= divisor;
}
return fraction.toString();
}
}
Input
numerator = 1, denominator = 2
Output
"0.5"
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const fractionToDecimal = function (numerator, denominator) {
if (numerator === 0) return '0'
let s = ''
if (Math.sign(numerator) !== Math.sign(denominator)) s += '-'
let n = Math.abs(numerator)
const d = Math.abs(denominator)
s += Math.floor(n / d)
n %= d
if (n === 0) return s
s += '.'
const map = {}
while (n !== 0) {
map[n] = s.length
n *= 10
s += Math.floor(n / d)
n %= d
const i = map[n] // repeat starting index
if (i != null) return `${s.slice(0, i)}(${s.slice(i)})`
}
return s
}
Input
numerator = 2, denominator = 1
Output
"2"
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def fractionToDecimal(self, n, d):
res = ["-"] if n * d < 0 else [""]
n, d = abs(n), abs(d)
res.append(str(n // d))
n %= d
if not n: return "".join(res)
res.append(".")
mp = {n: len(res)}
while n:
n *= 10
res.append(str(n // d))
n %= d
if n in mp:
res.insert(mp[n], "(")
res.append(")")
break
mp[n] = len(res)
return "".join(res)
Input
numerator = 2, denominator = 1
Output
"2"
#5 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode
{
public class _0166_FractionToRecurringDecimal
{
public string FractionToDecimal(int numerator, int denominator)
{
if (numerator == 0) return "0";
StringBuilder sb = new StringBuilder();
if (numerator < 0 ^ denominator < 0) sb.Append("-");
long dividend = Math.Abs((long)numerator);
long divisor = Math.Abs((long)denominator);
sb.Append((dividend / divisor).ToString());
long remainder = dividend % divisor;
if (remainder == 0) return sb.ToString();
sb.Append('.');
var map = new Dictionary < long, int>();
while (remainder != 0)
{
if (map.ContainsKey(remainder))
{
sb.Insert(map[remainder], "(");
sb.Append(")");
break;
}
map[remainder] = sb.Length;
remainder *= 10;
sb.Append((remainder / divisor).ToString());
remainder %= divisor;
}
return sb.ToString();
}
Input
numerator = 4, denominator = 333
Output
"0.(012)"