My clean Java solution


  • 174
    D

    The important thing is to consider all edge cases while thinking this problem through, including: negative integer, possible overflow, etc.

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

    Please comment if you see something wrong or can be improved. Cheers!

    public class Solution {
        public String fractionToDecimal(int numerator, int denominator) {
            if (numerator == 0) {
                return "0";
            }
            StringBuilder res = new StringBuilder();
            // "+" or "-"
            res.append(((numerator > 0) ^ (denominator > 0)) ? "-" : "");
            long num = Math.abs((long)numerator);
            long den = Math.abs((long)denominator);
            
            // integral part
            res.append(num / den);
            num %= den;
            if (num == 0) {
                return res.toString();
            }
            
            // fractional part
            res.append(".");
            HashMap<Long, Integer> map = new HashMap<Long, Integer>();
            map.put(num, res.length());
            while (num != 0) {
                num *= 10;
                res.append(num / den);
                num %= den;
                if (map.containsKey(num)) {
                    int index = map.get(num);
                    res.insert(index, "(");
                    res.append(")");
                    break;
                }
                else {
                    map.put(num, res.length());
                }
            }
            return res.toString();
        }
    }

  • 12
    C

    Nice !

    res.append(((numerator > 0) ^ (denominator > 0)) ? "-" : "");

  • 0
    L

    I think "res.append(((numerator > 0) ^ (denominator > 0)) ? "-" : "");" will get wrong answer for numerator=0 and denominator=1.


  • 1
    D

    Nice catch. But if numerator = 0, it would have been caught by the first if block.


  • 0
    B

    you do not need to evaluate res.length() each time. you can do int len=res.length(); and just len++ later on


  • 15
    J

    Great solution!

    You're reusing the variable num for the iterative calculation of the remainder. It would be better to introduce a remainder variable and use that instead, to make the code more clear:

        long remainder = num % den;
    

    Instead of writing map.put twice, you could refactor the while loop to do it only once.
    Also, instead of two lookups in the map with .containsKey and then .get,
    you could use just one .get and do a null check:

        while (num != 0) {
            map.put(num, res.length());
    
            num *= 10;
            res.append(num / den);
            num %= den;
    
            Integer remainderIndex = map.get(num);
            if (remainderIndex != null) {
                res.insert(remainderIndex, "(");
                res.append(")");
                break;
            }
        }
    

  • 0
    H

    I don't think using long would be a good idea... Cause what if you are asked to implement fractionToDecimal of 2 long in the real interview? (I don't have a solution for this by now btw)


  • 0
    C

    I think the code never handle "denominator ==0". But it should be a simple fix


  • 0
    M

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


  • 0
    L

    I think that is exactly what string.length() does!


  • 0

    This may save space caused by HashMap:

    HashMap<Long, Integer> map = new HashMap<Long, Integer>();
    map.put(num, res.length());
    

    changing to

    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    map.put((int)num, res.length());
    

  • 1
    class Solution {
    public:
        std::string fractionToDecimal(long long numerator, long long denominator) {
            if (!numerator)
                return "0";
            std::string str = numerator < 0 ^ denominator < 0 ? "-" : "";
            numerator = std::abs(numerator);
            denominator = std::abs(denominator);
            long long quotient = numerator / denominator, remainder = numerator % denominator;
            std::stringstream ss;
            ss << quotient;
            str += ss.str();
            if (!remainder)
                return str;
            str += '.';
            std::unordered_map<int, int> flag;
            int pos = str.size();
            while (remainder && flag.find(remainder) == flag.end()) {
                flag[remainder] = pos++;
                numerator = remainder * 10;
                quotient = numerator / denominator;
                remainder = numerator % denominator;
                str += '0' + quotient;
            }
            if (remainder) {
                str += ')';
                str.insert(str.begin() + flag[remainder], '(');
            }
            return str;
        }
    };

  • 0
    Y

    best solution I have seen so far in this thread. modularized and clear thought.


  • 0
    A
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    M

    Brilliant!
    Could anyone explain how this solution handles overflow? Thanks!


  • 0
    I
    This post is deleted!

  • 0

    Thanks for sharing! Here is my similar solution for reference.
    Deal with sign and integral part first, then combine with fraction as final result.

        public String fractionToDecimal(int numerator, int denominator) {
            long num = Math.abs((long) numerator);
            long denom = Math.abs((long) denominator);
            String integral = String.valueOf(num / denom);
            if ((numerator != 0) && ((numerator < 0) ^ (denominator < 0)))
                integral = "-" + integral;
    
            StringBuilder frac = new StringBuilder();
            Map<Long,Integer> map = new HashMap<>();
            for (int i = 0; num % denom != 0; i++) {
                num = (num % denom) * 10;
                if (map.putIfAbsent(num, i) != null) {
                    frac.insert(map.get(num), "(").append(")");
                    break;
                }
                frac.append(num / denom);
            }
            if (frac.length() == 0) return integral;
            return integral + "." + frac.toString();
        }
    

  • -1
    N

    Hi @dchen0215

    Thank you very much for your elegant solution. Do you have any thoughts on how you would handle pi(22/7). I have tested your code with pi and leetcode accepts it. But, as we know pi has never ending non-recurring fraction part. In real time scenario, how would you design your code to handle such cases


  • 1
    C

    @nikhilay All rational numbers will end up in cycles in decimal representation.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.