Sponsored
Sponsored
This method utilizes long division to compute the fraction part. We keep track of the remainder at each step using a hash map (or dictionary), which maps the remainder to its corresponding position in the decimal.
If a remainder repeats, it means the decimals will start repeating onwards, and we enclose the repeating sequence in parentheses.
Time Complexity: O(d), where d is the length of the repeating sequence in the worst case. This is because each fractional digit is calculated one at a time.
Space Complexity: O(d), for storing seen remainders in the hash map.
1import java.util.HashMap;
2
3public class Solution {
4 public String fractionToDecimal(int numerator, int denominator) {
5 if (numerator == 0) return "0";
6 StringBuilder result = new StringBuilder();
7 if ((numerator < 0) ^ (denominator < 0)) result.append("-");
8 long num = Math.abs((long) numerator);
9 long den = Math.abs((long) denominator);
10 result.append(num / den);
11 long remainder = num % den;
12 if (remainder == 0) return result.toString();
13 result.append(".");
14 HashMap<Long, Integer> map = new HashMap<>();
15 while (remainder != 0) {
16 if (map.containsKey(remainder)) {
17 result.insert(map.get(remainder), "(");
18 result.append(")");
19 break;
20 }
21 map.put(remainder, result.length());
22 remainder *= 10;
23 result.append(remainder / den);
24 remainder %= den;
25 }
26 return result.toString();
27 }
28}The Java solution follows the same logic as the Python approach, starting with handling the numerator being zero.
It maintains a StringBuilder for constructing the result and uses a HashMap to track previously seen remainders along with their positions in the result string, allowing us to detect repeating sequences.
If a repeating remainder is found, parentheses are inserted around the sequence before returning the result.