Last updated on January 21st, 2025 at 02:05 am
Here, we see a Fraction to Recurring Decimal LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Hash Table, Math
Companies
Level of Question
Medium
Fraction to Recurring Decimal LeetCode Solution
Table of Contents
1. 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.
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)”
2. Coding Pattern Used in Solution
The coding pattern used in this problem is “Hashing with Remainder Tracking”. The key idea is to use a hash map (or equivalent data structure) to track remainders during the division process to detect cycles and handle repeating decimals.
3. Code Implementation in Different Languages
3.1 Fraction to Recurring Decimal C++
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if(!numerator) return "0";
string ans = "";
if (numerator > 0 ^ denominator > 0) ans += '-';
long num = labs(numerator), den = labs(denominator);
long q = num / den;
long r = num % den;
ans += to_string(q);
if(r == 0) return ans;
ans += '.';
unordered_map<long, int> mp;
while(r != 0){
if(mp.find(r) != mp.end()){
int pos = mp[r];
ans.insert(pos, "(");
ans += ')';
break;
}
else{
mp[r] = ans.length();
r *= 10;
q = r / den;
r = r % den;
ans += to_string(q);
}
}
return ans;
}
};
3.2 Fraction to Recurring Decimal Java
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
boolean isNegative = (numerator < 0 && denominator > 0 || numerator > 0 && denominator < 0) ? true : false;
long numeratorL = Math.abs((long) numerator);
long denominatorL = Math.abs((long) denominator);
Map<Long, Integer> previousRemains = new HashMap<Long, Integer>();
StringBuilder sb = new StringBuilder();
long quotian = numeratorL / denominatorL;
sb.append(quotian);
numeratorL %= denominatorL;
if (numeratorL != 0) {
sb.append(".");
}
int quotianIndex = 0;
while (numeratorL != 0) {
numeratorL *= 10;
quotian = Math.abs(numeratorL / denominatorL);
if (!previousRemains.containsKey(numeratorL)) {
sb.append(quotian);
previousRemains.put(numeratorL, quotianIndex++);
} else {
int firstIndex = 1 + previousRemains.get(numeratorL) + sb.indexOf(".");
sb.insert(firstIndex, '(');
sb.append(")");
break;
}
numeratorL %= denominatorL;
}
if (isNegative) {
sb.insert(0, "-");
}
return sb.toString();
}
}
3.3 Fraction to Recurring Decimal JavaScript
var fractionToDecimal = function(numerator, denominator) {
if(!numerator) return '0';
let str = '';
if(Math.sign(numerator) !== Math.sign(denominator)) str += '-';
const numer = Math.abs(numerator)
const denom = Math.abs(denominator)
str += Math.floor(numer/denom);
let rem = numer%denom;
if(!rem) return str;
str += '.'
const map = new Map();
while(rem !== 0) {
map.set(rem, str.length);
rem *= 10;
str += Math.floor(rem/denom);
rem %= denom
if(map.has(rem)) {
const idx = map.get(rem);
return str.slice(0, idx) + `(${str.slice(idx)})`;
}
}
return str;
};
3.4 Fraction to Recurring Decimal Python
class Solution(object):
def fractionToDecimal(self, numerator, denominator):
n, remainder = divmod(abs(numerator), abs(denominator))
sign = '-' if numerator*denominator < 0 else ''
result = [sign+str(n), '.']
stack = []
while remainder not in stack:
stack.append(remainder)
n, remainder = divmod(remainder*10, abs(denominator))
result.append(str(n))
idx = stack.index(remainder)
result.insert(idx+2, '(')
result.append(')')
return ''.join(result).replace('(0)', '').rstrip('.')
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |
- The code uses a hash map (or equivalent) to detect cycles in the fractional part of the division.
- The time complexity is linear with respect to the number of unique remainders.
- The space complexity is also linear due to the storage of remainders in the hash map (or equivalent).