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)".

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Hash Table Math

---------------------------------------------------------------

---------------------------------------------------------------

1. Using normal dividing method: 

    0.16  
6 ) 1.00
    0 
    1 0       <-- Remainder=1, mark 1 as seen at position=0.
    - 6 
      40      <-- Remainder=4, mark 4 as seen at position=1.
    - 36 
       40      <-- Remainder=4 was seen before at position=1, 
so the fractional part which is 16 starts repeating at position=1 => 1(6).

2. take care the extreme input case:

-2147483648 / -1 ---in such case, it should be use long long to deal with it.

related information about above case:

~~~~~~~~~~~~~~~~~~~~`

Practically, this occurs when the programmer is trying to express the minimum integer value, which is -2147483648. This value cannot be written as -2147483648 because the expression is processed in two stages:

1. The number 2147483648 is evaluated. Because it is greater than the maximum integer value of 2147483647, the type of 2147483648 is not int, but unsigned int.
2. Unary minus is applied to the value, with an unsigned result, which also happens to be 2147483648.

The unsigned type of the result can cause unexpected behavior. If the result is used in a comparison, then an unsigned comparison might be used, for example, when the other operand is an int. This explains why the example program below prints just one line.

The expected second line, 1 is greater than the most negative int, is not printed because ((unsigned int)1) > 2147483648 is false.

~~~~~~~~~~~~~~~~~~~~

//////////////////////////////////////////////////

//code

class Solution {

 public:

        string fractionToDecimal(long long numerator, long long denominator) {

               string final;

               //sign

               if (numerator<0 && denominator>0 || numerator>0 && denominator<0) final.push_back('-');

               //integer part

               long long inte = numerator / denominator;

               final += to_string(inte);

               //fraction part       

               inte = (numerator%denominator) * 10;

               if (inte == 0)return final;

               else final += '.';

               unordered_map<long long, char> remain;

               while (inte != 0){

                      if (remain.find(inte) == remain.end()) {

                            long long tmp = inte / denominator;

                            remain[inte] = tmp + '0';

                      }

                      else{

                            //there is repeating

                            for (unordered_map<long long, char>::iterator it = remain.begin(); it != remain.end(); it++){

                                   if (it->first != inte){

                                          final += it->second;

                                   }

                                   else{

                                          final += '(';

                                          final += it->second;

                                   }

                            }

                            final += ')';

                            return final;

                      }

                      inte = inte%denominator * 10;

               }

               //no repeating

               for (unordered_map<long long, char>::iterator it = remain.begin(); it != remain.end(); it++)final += it->second;

               return final;

        }

 };