Fastest Java solution (1 ms) and O(1) space


  • 2
    L

    My algorithm base on the Floyd's cycle-finding algorithm. Instead of using hashMap to store the result of each step, It uses two pointer, fast (iterate twice each time) and slow (iterate once each time) to detect cycle. Then It finds out the non-cycle part and cycle part. Therefore, it's O(1) space and is faster than those of using hash.

    public class Solution {
        public String fractionToDecimal(int numerator, int denominator) {
            // negative sign
            boolean negative = (numerator < 0) ^ (denominator < 0);
            long n = Math.abs((long)numerator);
            long d = Math.abs((long)denominator);
            long intPart = n / d;
            long rest = n - intPart * d;
            if (rest == 0) return negative ? String.valueOf(intPart * (-1)) : String.valueOf(intPart); // Integer result
            StringBuilder res = new StringBuilder();
            if (negative) res.append("-");
            res.append(intPart);
            res.append(".");
            long slow;
            long fast;
            long[] temp = new long[2];
            slow = Decimal(rest*10, d)[1];
            fast = Decimal(Decimal(rest*10, d)[1], d)[1];
            while (slow != fast) {
                slow = Decimal(slow, d)[1];
                fast = Decimal(Decimal(fast, d)[1], d)[1];
            }
            slow = rest * 10;
            while (slow != fast && slow != 0) {
                temp = Decimal(slow, d);
                slow = temp[1];
                res.append(temp[0]);       // non-cycle part
                fast = Decimal(fast, d)[1];
            }
            if (slow == 0) return res.toString();  // return when result is finite decimal
            temp = Decimal(slow, d);
            fast = temp[1];
            res.append("(");
            res.append(temp[0]);
            while (slow != fast) {
                temp = Decimal(fast, d);
                fast = temp[1];
                res.append(temp[0]);  // cycle part
            }
            res.append(")");
            return res.toString();
        }
        public long[] Decimal(long rest, long denominator) {
            // return the quotient and remainder (multiplied by 10)
            long r1;
            long r2;
            if (rest < denominator) {
                r1 = 0;
                r2 = rest * 10;
            }
            else {
                r1 = rest / denominator;
                r2 = (rest - denominator * r1) * 10;
            }
            return new long[]{r1, r2};
        }
    }
    

Log in to reply
 

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