## Similar Problems

Similar Problems not available

# Fraction To Recurring Decimal - Leetcode Solution

## Companies:

LeetCode: Fraction To Recurring Decimal Leetcode Solution

Difficulty: Medium

Topics: math hash-table string

Problem Statement:

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.

Example 1:

Input: numerator = 1, denominator = 2

Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1

Output: "2"

Example 3:

Input: numerator = 2, denominator = 3

Output: "0.(6)"

Example 4:

Input: numerator = 4, denominator = 333

Output: "0.(012)"

Example 5:

Input: numerator = 1, denominator = 5

Output: "0.2"

Constraints:

-2^31 <= numerator, denominator <= 2^31 - 1

denominator != 0

Solution:

Let's start by analyzing some examples. Let's look at the case of 1/2. The result is 0.5. Let's now look at the case of 2/3. The result is 0. (6), which means that the result is 0.666... and the 6 is repeating.

To solve the problem, we need to keep track of the remainder at each step. We can do this by creating a map that maps the remainder to the position where it occurs. At each step, we divide the numerator by the denominator and get the quotient and remainder. We append the quotient to the result string and then check if the remainder is already in the map. If it is, we enclose the repeating part in parentheses and return the result. If it is not, we add it to the map and continue with the next step.

Let's see the implementation of the above approach:

class Solution:

```
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
if numerator == 0:
return "0"
res = ""
if (numerator < 0 and denominator > 0) or (numerator > 0 and denominator < 0):
res += "-"
numerator = abs(numerator)
denominator = abs(denominator)
res += str(numerator//denominator)
remainder = numerator % denominator
if remainder == 0:
return res
res += "."
map = {}
while remainder != 0:
if remainder in map:
index = map[remainder]
res = res[:index] + "(" + res[index:] + ")"
break
map[remainder] = len(res)
remainder *= 10
res += str(remainder//denominator)
remainder %= denominator
return res
```

The time complexity of the above solution is O(N) where N is the maximum number of digits in the result. The space complexity is O(N) as well, since we need to keep track of the remainder at each step in the map.

## Fraction To Recurring Decimal Solution Code

`1`