[Leetcode] Fraction to Recurring Decimal

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.

For example,

  • Given numerator = 1, denominator = 2, return “0.5”.
  • Given numerator = 2, denominator = 1, return “2”.
  • Given numerator = 2, denominator = 3, return “0.(6)”.

Hint:

  1. No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
  2. Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
  3. Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

Java Solution

The important thing is to consider all edge cases: negative integer, possible overflow, etc.

We can use a HashMap to store the remainder and its associated index while doing the division so that whenever the same remainder comes up, we know there is a repeating fractional part.

long is used to handle cases where numerator or denominator is equal to maximum negative integer. Otherwise the absolute value will be incorrect.