Leetcode: Fraction to Recurring Decimal

 This question was asked mainly at Goldman Sachs and IXL and actually has an extremely low passing rate, due to the edge cases, and in my opinion, should be a Leetcode Hard, since only 20% of people managed to pass this problem. 

The question is as follows:

Given two integers representing the numerator and denominator of a fraction, return the fraction in a string format. If the fractional part is repeating, enclose the repeating part in parentheses. If multiple answers are possible, return any of them and the length of an answer of a string is less than 10^4 for all the given inputs.  

The numerator is from -2^31 to 2^31 - 1 and the denominator does not equal to 0.

Here are some examples:

Example 1:

Input: numerator = 1, denominator = 2

Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1

Output: "2"

Example 3:

Input: numerator = 2, denominator = 3

Output: "0.(6)"

Example 4:

Input: numerator = 4, denominator = 333

Output: "0.(012)"

Example 5:

Input: numerator = 1, denominator = 5

Output: "0.2" 

And the hints are as follows:

1. No scary math, just apply elementary math knowledge. Still remember how to perform a long division?

2. Try long division on 4/9 and then try 4/333. Do you see a pattern? 

3. Notice that once the remainder starts repeating, so does the divided result.

 4. Be wary of edge cases. List out as many test cases you can think of and test your code thoroughly. 

One thing I can do is to notice once the remainder is repeating, so does the starting result. 

So the first thing we do is to figure out if one of the numbers are negative, using the xor function then append a negative sign to it. The rest of the time, I perform simple second grade school division. It has a new hashmap that contains the remainder keys and see if the map contains the particular keys. 

Here's the code:

public String fraction ToDecimal(int numerator, int denominator) {

    if(numerator == 0) return "0";

    StringBuilder fraction = new StringBuilder();

    //append - if one or the other is negative.

    if(numerator < 0 ^ denominator < 0) fraction.append("-");

    long dividend = Math.abs(Long.valueOf(numerator));

    long divisor = Math.abs(Long.valueOf(denominator));

    //append just the division "/"

    fraction.append(String.valueOf(dividend / divisor));

    //get remainder 

    long remainder = dividend % divisor;

    if(remainder == 0) return fraction.toString();

    //decimal sign

    fraction.append(".");

    //keeps track of the positions of the remainders

    Map<Long, Integer> map = new HashMap<>();

    while(remainder != 0) {

        //If remainder is contained, go to index of first remainder and put "(" around it

        if(map.containsKey(remainder)) {

            fraction.insert(map.get(remainder), "(");

            fraction.append(")");

            break;

        }

        //Get remainder, multiply by 10, and perform the division again

        map.put(remainder, fraction.length());

        remainder *= 10;

        fraction.append(String.valueOf(remainder / divisor);

        remainder % divisor;

    }

    return fraction.toString();

}

To understand the logic behind this, we'll have to dig into the StringBuilder method insert. In this problem, the solution is inserted into the remainder index, which is basically just inserting the item "(" right before the reminder surfaces.