## 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 - 1
• denominator != 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;
}
Copy The Code &

Input

cmd
numerator = 1, denominator = 2

Output

cmd
"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();
}
}
Copy The Code &

Input

cmd
numerator = 1, denominator = 2

Output

cmd
"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
}
Copy The Code &

Input

cmd
numerator = 2, denominator = 1

Output

cmd
"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)
Copy The Code &

Input

cmd
numerator = 2, denominator = 1

Output

cmd
"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();
}

Copy The Code &

Input

cmd
numerator = 4, denominator = 333

Output

cmd
"0.(012)"