Fraction to Recurring Decimal in Java
We must return a fraction in string format given two numbers that represent the fraction's numerator and denominator. If there is a recurring portion in the factorial, we put it in parentheses.
Example 1:
Input:
Numerator: 3 Denominator: 4
Output: "0.75"
Explanation: Here the when we divide the numerator with denominator we get a perfect decimal. So we return the ouput "0.75"
Input:
Numerator: 2 Denominator: 3
Output: " 0.(6)"
Explanation: Here the when we divide the numerator with denominator we do not get a perfect decimal. So we keep the recurring number in parentheses and return the value as " 0.(6)".
Long Division Approach
In this approach, the decimal component is appended, the fractional part is handled by computing remainders and attaching digits, and recurrent patterns in the fractional part are identified through the use of a hash map.
FileName: FractionToRecurringDecimal.java
import java.util.HashMap; import java.util.Map; public class FractionToRecurringDecimal { public static String fractionToDecimal(int numerator, int denominator) { if (numerator == 0) return "0"; // If numerator is zero, return "0" StringBuilder result = new StringBuilder(); // Handle the sign result.append((numerator > 0) ^ (denominator > 0) ? "-" : ""); long num = Math.abs((long) numerator); long den = Math.abs((long) denominator); // Append the integer part result.append(num / den); num %= den; if (num == 0) return result.toString(); // Append the fractional part result.append("."); Map map = new HashMap<>(); map.put(num, result.length()); while (num != 0) { num *= 10; result.append(num / den); num %= den; if (map.containsKey(num)) { int index = map.get(num); result.insert(index, "("); result.append(")"); break; } else { map.put(num, result.length()); } } return result.toString(); } public static void main(String[] args) { int numerator = 2; int denominator = 3; System.out.println(fractionToDecimal(numerator, denominator)); int numerator1 = 2; int denominator1 = 4; System.out.println(fractionToDecimal(numerator1, denominator1)); } }
Output:
0.(6) 0.5
Complexity Analysis:
Time Complexity: O(n), where n is the number of digits in the resulting decimal.
Space Complexity: O(n+den), where n is the number of digits in the resulting decimal and den is the denominator of the fraction.