Leetcode 166. Fraction to Recurring Decimal

Problem Explanation

We need to find the decimal representation of the division of two numbers (a numerator and denominator). If the decimal part repeats we should represent the repeating section in parentheses.

For example, let's consider this scenario:

If we have a numerator of 2 and a denominator of 3 the result of their division is 0.6666..., the decimal part repeats the 6 so the representation should be 0.(6).

Solution Approach

We can start this problem by dividing the numerator by the denominator to get the integer part of the result. An edge case that we need to consider early on is that if the numerator is 0, the result should be 0.

We also need to consider whether the result is negative. The result is negative only if exactly one of the numbers is negative (because a positive divided by a positive or a negative divided by a negative both yield a positive result).

We can handle the integer part of the result first. Then, we can handle the decimal part.

To handle the decimal part, we take the remainder of the division and check if it's 0, if it's 0 we're done. Otherwise, we begin to perform the division manually, digit by digit. For each remainder, we check if we have seen it before, if we have, we found a sequence that repeats and we can stop.

Walkthrough Example

Let's walk through an example with a numerator of 4 and a denominator of 333.

  1. Divide 4 by 333. First, we get a 0 and a remainder of 4.
  2. Check that the remainder is not 0 and take the remainder (4), multiply it by 10 (40) and divide it by 333.
  3. We get a 0 again and a remainder of 40, multiply the remainder by 10 (400) and divide it by 333.
  4. We get a 1 and a remainder of 67, multiply the remainder by 10 (670) and divide it by 333.
  5. We get a 2 and a remainder of 4. We have arrived again at the remainder 4, this means that the sequence will start repeating after this.
  6. The final result is 0.012 with the 012 repeating. So, we represent it as 0.(012).

Python Solution

1
2python
3class Solution:
4    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
5        n, remainder = divmod(abs(numerator), abs(denominator))
6        sign = '-' if numerator * denominator < 0 else ''
7        result = [sign + str(n), '.']
8        stack = []
9        seen = {}
10
11        while remainder not in seen:
12            seen[remainder] = len(stack)
13            n, remainder = divmod(remainder * 10, abs(denominator))
14            stack.append(str(n))
15
16        i = seen[remainder]
17        result.extend(stack[:i])
18        result.append('(')
19        result.extend(stack[i:])
20        result.append(')')
21
22        return ''.join(result).replace('(0)', '').rstrip('.')

Java Solution

1
2java
3class Solution {
4    public String fractionToDecimal(int numerator, int denominator) {
5        if (numerator == 0) return "0";
6
7        StringBuilder res = new StringBuilder();
8        boolean isNegative = (numerator > 0) ^ (denominator > 0);
9        if (isNegative) res.append("-");
10
11        long num = Math.abs((long) numerator);
12        long den = Math.abs((long) denominator);
13        
14        res.append(num / den);
15        num %= den;
16
17        if (num == 0) return res.toString();
18
19        res.append(".");
20        Map<Long, Integer> map = new HashMap<>();
21        while(num != 0) {
22            map.put(num, res.length());
23            num *= 10;
24            res.append(num / den);
25            num %= den;
26            
27            if (map.containsKey(num)) {
28                int index = map.get(num);
29                res.insert(index, "(");
30                res.append(")");
31                break;
32            }
33        }
34
35        return res.toString();
36    }
37}

JavaScript Solution

1
2javascript
3let fractionToDecimal = function(numerator, denominator) {
4    if(numerator === 0) return "0";
5    let result = '';
6    result += ((numerator > 0) ^ (denominator > 0)) ? '-' : '';
7    numerator = Math.abs(numerator);
8    denominator = Math.abs(denominator);
9    result += Math.floor(numerator / denominator);
10    numerator %= denominator;
11    if(numerator === 0) return result;
12    result += '.';
13    let map = {};
14    map[numerator] = result.length;
15    while(numerator !== 0) {
16        numerator *= 10;
17        result += Math.floor(numerator / denominator);
18        numerator %= denominator;
19        if(map[numerator] !== undefined) {
20            let index = map[numerator];
21            result = result.substr(0, index) + '(' + result.substr(index) + ')';
22            return result;
23        } else {
24            map[numerator] = result.length;
25        }
26    }
27    return result;
28};

C++ Solution

1
2cpp
3class Solution {
4public:
5    string fractionToDecimal(int numerator, int denominator) {
6        if (!numerator) return "0";
7        string res;
8        if ((numerator > 0) ^ (denominator > 0)) res += '-';
9        long num = labs(numerator), den = labs(denominator);
10        res += to_string(num / den);
11        num %= den;
12        if (!num) return res;
13        res += '.';
14        unordered_map<int, int> m;
15        while (num) {
16            num *= 10;
17            auto [iter, isNew] = m.emplace(num, res.size());
18            if (!isNew) {
19                res.insert(iter -> second, "(");
20                res += ')';
21                break;
22            }
23            res += to_string(num / den);
24            num %= den;
25        }
26        return res;
27    }
28};

C# Solution

1
2csharp
3public class Solution {
4    public string FractionToDecimal(int numerator, int denominator) {
5        if (numerator == 0) return "0";
6        StringBuilder res = new StringBuilder();
7        res.Append((numerator > 0) ^ (denominator > 0) ? "-" : "");
8        long num = Math.Abs((long)numerator);
9        long den = Math.Abs((long)denominator);
10
11        res.Append(num / den);
12        num %= den;
13        if (num == 0) return res.ToString();
14
15        res.Append(".");
16        Dictionary<long, int> map = new Dictionary<long, int>();
17        map[num] = res.Length;
18        while (num != 0){
19            num *= 10;
20            res.Append(num / den);
21            num %= den;
22            if (map.ContainsKey(num)){
23                int index = map[num];
24                res.Insert(index, "(");
25                res.Append(")");
26                break;
27            }
28            else{
29                map[num] = res.Length;
30            }
31        }
32        return res.ToString();
33    }
34}

As we can observe from above, the solutions in Python, Java, and JavaScript majorly rely on similar logic. They first obtain the integer part and when it comes to the decimal part of the result, they progressively perform division operation for each remainder. Once a repeating remainder is found, the loop terminates.

Although the coding language varies, the implementation approach is closely similar across all the presented languages.

The strings that consist of the result are structured as per requirements. In Python, Java, JavaScript, we append characters to a string and perform string manipulations to achieve desired result.

In java, HashMap is used to store the remainders and its count whereas in Python, JavaScript a dictionary (in form of an object in JavaScript) is used. The reason for selecting these data structures is their constant time complexity for fetching and storing operations.

In terms of space complexity, all the solutions above have O(N) space complexity because potentially, each digit in the decimal part of the result needs to be stored. In terms of time complexity, during the main loop of the algorithms, we perform the division operation once for each digit, hence, the time complexity is also O(N).

These solutions are efficient and demonstrate good use of data structures and basic programming constructs. Hence, they serve as good examples for tackling mathematical problems with repeated operations.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫