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)"
Constraints:
-231 <= numerator, denominator <= 231 - 1denominator != 0To solve Fraction to Recurring Decimal, the goal is to convert a fraction represented by numerator and denominator into its decimal string form while correctly identifying repeating sequences. The key challenge is detecting when the fractional part starts repeating.
First handle edge cases such as negative values and zero numerator. Compute the integer part of the division and then process the remainder to build the decimal portion. During the long division simulation, store each remainder and its position in a Hash Map. If the same remainder appears again, it indicates the start of a repeating cycle. At that index, insert an opening parenthesis and append a closing parenthesis at the end.
This method effectively tracks repeating patterns because identical remainders produce identical future digits in long division. The approach ensures correct formatting of the decimal representation while efficiently identifying cycles. The algorithm runs in linear time relative to the number of digits generated and uses additional space to track remainders.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map with Long Division Simulation | O(n) | O(n) |
Cognito
Use these hints if you're stuck. Try solving on your own first.
No scary math, just apply elementary math knowledge. Still remember how to perform a <i>long division</i>?
Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
Notice that once the remainder starts repeating, so does the divided result.
Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.
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) {
5The 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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Repeating decimals occur when the same remainder appears again during long division. Once a remainder repeats, the digits that follow will repeat in the same pattern indefinitely.
Yes, this problem or its variations are common in technical interviews because it tests knowledge of hash tables, number manipulation, and careful handling of edge cases such as negatives and overflow.
A hash map is the most useful data structure because it maps each remainder to the index where it first appeared in the result string. This makes it easy to detect repeating sequences and mark them correctly.
The optimal approach simulates long division while storing previously seen remainders in a hash map. When a remainder repeats, it indicates the start of a repeating decimal cycle, allowing you to insert parentheses around the repeating digits.