Description
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.
Examples:
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)"Solution in Python
Certainly! To solve the problem of converting a fraction to a decimal representation with repeating parts enclosed in parentheses, we need to handle the following steps:
- Handle edge cases: If the numerator is zero, the result is “0”.
- Determine the sign: The result is negative if one of the numerator or denominator is negative, but not both.
- Convert to positive: Work with the absolute values of the numerator and denominator.
- Calculate the integral part: Perform integer division of the numerator by the denominator.
- Calculate the fractional part: Use the remainder of the integer division to calculate the decimal part.
- Detect repeating sequences: Use a dictionary to keep track of seen remainders and their corresponding positions in the fractional part. If a remainder repeats, it indicates the start of a repeating sequence.
- Format the result: Combine the integral and fractional parts, and insert parentheses around the repeating sequence if detected.
Python
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
if numerator == 0:
return "0"
result = []
# Determine the sign
if (numerator < 0) ^ (denominator < 0):
result.append("-")
# Work with absolute values
numerator = abs(numerator)
denominator = abs(denominator)
# Calculate the integral part
integral_part = numerator // denominator
result.append(str(integral_part))
# Calculate the remainder
remainder = numerator % denominator
if remainder == 0:
return ''.join(result) # No fractional part
# Add the decimal point for the fractional part
result.append(".")
# Dictionary to store the remainder positions
remainder_dict = {}
# List to store the fractional digits
fractional_part = []
while remainder != 0:
# If the remainder is already seen, we have a repeating part
if remainder in remainder_dict:
# Insert the opening parenthesis
fractional_part.insert(remainder_dict[remainder], "(")
fractional_part.append(")")
break
# Record the position of this remainder
remainder_dict[remainder] = len(fractional_part)
# Multiply remainder by 10 for the next digit
remainder *= 10
fractional_part.append(str(remainder // denominator))
remainder %= denominator
# Combine the integral and fractional parts
result.extend(fractional_part)
return ''.join(result)Explanation of Key Parts:
- Sign determination:
if (numerator < 0) ^ (denominator < 0)checks if exactly one of the numerator or denominator is negative. - Integral part:
numerator // denominatorcalculates the integral part. - Remainder calculation:
remainder = numerator % denominatoris used to find the initial remainder. - Repeating part detection:
remainder_dictstores remainders and their positions in the fractional part list. If a remainder repeats, it means the fractional part starts repeating from that position. - Fractional part construction: As long as the remainder is not zero, it keeps calculating the next digit and updating the remainder. When a remainder repeats, it inserts parentheses around the repeating sequence.
Solution in Javascript
JavaScript
/**
* @param {number} numerator
* @param {number} denominator
* @return {string}
*/
var fractionToDecimal = function(numerator, denominator) {
// Handle edge case where numerator is zero
if (numerator === 0) {
return "0";
}
let result = [];
// Determine the sign of the result
if (Math.sign(numerator) !== Math.sign(denominator)) {
result.push("-");
}
// Work with absolute values of numerator and denominator
numerator = Math.abs(numerator);
denominator = Math.abs(denominator);
// Calculate the integral part
let integralPart = Math.floor(numerator / denominator);
result.push(integralPart.toString());
// Calculate the remainder
let remainder = numerator % denominator;
if (remainder === 0) {
return result.join(""); // No fractional part
}
// Add the decimal point for the fractional part
result.push(".");
// Dictionary to store the remainder positions
let remainderDict = new Map();
// Array to store the fractional digits
let fractionalPart = [];
while (remainder !== 0) {
// If the remainder is already seen, we have a repeating part
if (remainderDict.has(remainder)) {
// Insert the opening parenthesis
fractionalPart.splice(remainderDict.get(remainder), 0, "(");
fractionalPart.push(")");
break;
}
// Record the position of this remainder
remainderDict.set(remainder, fractionalPart.length);
// Multiply remainder by 10 for the next digit
remainder *= 10;
fractionalPart.push(Math.floor(remainder / denominator).toString());
remainder %= denominator;
}
// Combine the integral and fractional parts
result.push(...fractionalPart);
return result.join("");
};Solution in Java
Java
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
// Handle the edge case where the numerator is zero
if (numerator == 0) {
return "0";
}
StringBuilder result = new StringBuilder();
// Determine the sign of the result
if ((numerator < 0) ^ (denominator < 0)) {
result.append("-");
}
// Work with absolute values of numerator and denominator
long num = Math.abs((long) numerator);
long denom = Math.abs((long) denominator);
// Calculate the integral part
long integralPart = num / denom;
result.append(integralPart);
// Calculate the remainder
long remainder = num % denom;
if (remainder == 0) {
return result.toString(); // No fractional part
}
// Add the decimal point for the fractional part
result.append(".");
// Map to store remainders and their positions in the fractional part
Map<Long, Integer> remainderMap = new HashMap<>();
// StringBuilder to store the fractional digits
StringBuilder fractionalPart = new StringBuilder();
while (remainder != 0) {
// If the remainder is already seen, we have a repeating part
if (remainderMap.containsKey(remainder)) {
// Insert the opening parenthesis
int position = remainderMap.get(remainder);
fractionalPart.insert(position, "(");
fractionalPart.append(")");
break;
}
// Record the position of this remainder
remainderMap.put(remainder, fractionalPart.length());
// Multiply remainder by 10 for the next digit
remainder *= 10;
fractionalPart.append(remainder / denom);
remainder %= denom;
}
// Combine the integral and fractional parts
result.append(fractionalPart);
return result.toString();
}
}Solution in C#
C#
using System;
using System.Collections.Generic;
public class Solution {
public string FractionToDecimal(int numerator, int denominator) {
// Handle the edge case where the numerator is zero
if (numerator == 0) {
return "0";
}
// Initialize result string
StringBuilder result = new StringBuilder();
// Determine the sign of the result
if ((numerator < 0) ^ (denominator < 0)) {
result.Append("-");
}
// Work with absolute values to simplify calculations
long num = Math.Abs((long)numerator);
long denom = Math.Abs((long)denominator);
// Calculate the integral part of the division
long integralPart = num / denom;
result.Append(integralPart);
// Calculate the remainder
long remainder = num % denom;
if (remainder == 0) {
return result.ToString(); // No fractional part
}
// Add the decimal point for the fractional part
result.Append(".");
// Dictionary to store remainders and their positions in the fractional part
Dictionary<long, int> remainderMap = new Dictionary<long, int>();
// StringBuilder to build the fractional part
StringBuilder fractionalPart = new StringBuilder();
while (remainder != 0) {
// If the remainder is already seen, we have a repeating part
if (remainderMap.ContainsKey(remainder)) {
// Insert the opening parenthesis
int position = remainderMap[remainder];
fractionalPart.Insert(position, "(");
fractionalPart.Append(")");
break;
}
// Record the position of this remainder
remainderMap[remainder] = fractionalPart.Length;
// Multiply remainder by 10 for the next digit
remainder *= 10;
fractionalPart.Append(remainder / denom);
remainder %= denom;
}
// Combine the integral and fractional parts
result.Append(fractionalPart);
return result.ToString();
}
}