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

• 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};
}
}
``````

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