Fraction to Recurring Decimal

Description

https://leetcode.com/problems/fraction-to-recurring-decimal/description/

Solution

Pay attention to the fact that the pair of quote plus redundant in each divide iteration is the feature to judge whether the loop happened. Based on which, We ssing a list to record the order of the pair list, and maintain a set to judge whether the pair is occupied in each iteration. Once it was in the set, we stop it. Then we traverse the pair list to find the loop part and the unloop part.

class Pair {
    private long quote;
    private long remain;
    public Pair(long quote, long remain) {
        this.quote = quote;
        this.remain = remain;
    }
    
    public long getQuote() {
        return this.quote;
    }
    
    public long getRemain() {
        return this.remain;
    }
    @Override
    public int hashCode(){
        return (int) (this.quote * this.remain);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if(obj instanceof Pair) {
            return ( (Pair)obj ).remain == this.remain && (( (Pair)obj ).getQuote() == this.quote);
        }
        return false;
    }
}


public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        StringBuilder ret = new StringBuilder();
        ArrayList<Character> integerList = new ArrayList();
        HashSet<Pair> remainQuoteSet = new HashSet<>();
        ArrayList<Pair> remainQuoteList = new ArrayList<>();
        
        long longNumerator = (long) numerator;
        long longDenominator = (long) denominator;
        if (longNumerator*longDenominator < 0) ret.append('-');
        longNumerator = Math.abs(longNumerator);
        longDenominator = Math.abs(longDenominator);
        long quote = longNumerator / longDenominator;
        long remain = longNumerator % longDenominator;

        //Process Integer
        do{
            integerList.add( (char) (quote % 10 + '0') );
            quote /= 10;
        }while(quote > 0);
        for (int index = integerList.size()-1; index >= 0; index -= 1){
            ret.append(integerList.get(index));
        }
        
        if (remain == 0) {
            return ret.toString();
        }
        
        ret.append(".");
        
        //Process Decimal
        quote = remain * 10 / longDenominator;
        remain = remain * 10 % longDenominator;
        Pair pair = new Pair(quote, remain);
        while(remainQuoteSet.contains(pair) == false) {
            remainQuoteSet.add(pair);
            remainQuoteList.add(pair);
            quote = remain * 10 / longDenominator;
            remain = remain * 10 % longDenominator;
            pair = new Pair(quote, remain);
        }
        
        int beginIndexOfLoop = remainQuoteList.indexOf(pair);
        //Find the unloop section
        for (int index = 0; index < beginIndexOfLoop; index += 1) {
            ret.append( (char) (remainQuoteList.get(index).getQuote() + '0') );
        }
        
        //Find the loop section
        if (remain != 0) {
            ret.append('(');
            for (int index = beginIndexOfLoop; index < remainQuoteList.size(); index += 1) {
                ret.append( (char) (remainQuoteList.get(index).getQuote() + '0') );
            }
            ret.append(')');
        } 
        
        System.out.println(remainQuoteList);
        return ret.toString();
    }
}

Attention

1. In java, you can use the class as the key word in the map(set), but to make them work functionally, you need some extra effort——override the hashCode and equals methods in the class.
2. The corner case of big int can reduce to some awkward situation, so my suggestion is convert the parmeter to long type.