Header Ad

Leetcode Fraction to Recurring Decimal problem solution

In this Leetcode Fraction to Recurring Decimal problem solution we have 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. If multiple answers are possible, return any of them. It is guaranteed that the length of the answer string is less than 104 for all the given inputs.

Leetcode Fraction to Recurring Decimal problem solution


Problem solution in Python.

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        stack=[]
        symbol=True
        if numerator<0:
            symbol=not symbol
            numerator=-numerator
        if denominator<0:
            symbol=not symbol
            denominator=-denominator
        if not symbol and numerator!=0:
            stack.append('-')
        quotient,remainder=divmod(numerator,denominator)
        
        stack.append(str(quotient))
        if remainder==0:
            return ''.join(stack)
        
        remainder_map={}
        stack.append('.')
        while(True):
            if remainder in remainder_map:
                stack.insert(remainder_map[remainder],'(')
                stack.append(')')
                return ''.join(stack)
            if remainder==0:
                return ''.join(stack)
            remainder_map[remainder]=len(stack)
            remainder=remainder*10
            quotient,remainder=divmod(remainder,denominator)
            stack.append(str(quotient))



Problem solution in Java.

class Solution {

static long gcd(long a, long b) 
{ 
  if (b == 0) 
    return a; 
  return gcd(b, a % b);  
} 

public String fractionToDecimal(int numerator, int denominator) {
    
    HashMap<Pair<Long,Long>,Integer> Hmp = new HashMap<Pair<Long,Long>,Integer> ();
    String ans = new String("");
    if(numerator==0)
        return "0";
    boolean neg = (numerator<0)^(denominator<0);
    if(neg)
        ans+="-";
    long n = Math.abs((long)numerator);
    long d = Math.abs((long)denominator);
    long g = gcd(n,d);
    n /= g;
    d /= g;
    long m = n/d;
    ans+=String.valueOf(m);
    
    n = n - m*d;
    if(n!=0)
        ans+=".";
    
    while(n!=0){
        n = n*10;
        g = gcd(n,d);
        n /= g;
        d /= g;
        m =  n/d;
        Pair <Long, Long> key = new Pair <Long, Long>(new Long(n),new Long(d));
        if(Hmp.containsKey(key)){
            int idx = Hmp.get(key).intValue();
            return ans.substring(0, idx) + "(" + ans.substring(idx) + ")";
        }
        else{
            ans += String.valueOf(m);
            Hmp.put(key,new Integer(ans.length()-1));
        }
        n = n - m*d;
    }
    
    return ans;
}
}


Problem solution in C++.

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        long long int denominator1=denominator;
        long long int numerator1=numerator;
        if(!numerator1)
        {
            return "0";
        }
        if(denominator==1)
        {
            return to_string(numerator);
        }
        long long int t;
        if(denominator==-1)
        {
            t=-1*numerator1;
            return to_string(t);
        }
        int minus(0);
        if(numerator1<0&&denominator1>0)
        {
            minus=1;
            numerator1*=-1;
        }
        else if(numerator1>0&&denominator1<0)
        {
            minus=1;
            denominator1*=-1;
        }
        else if(numerator1<0&&denominator1<0)
        {
            numerator1*=-1;
            denominator1*=-1;
        }
        string result;
        unordered_map<int,int> record;

        long long int dividend=numerator1;
        int flag(0);
        int count(0);
        while(dividend!=0)
        {
            if(dividend<denominator1)
            {
                if(record[dividend]!=0)
                {
                    flag=2;
                    break;
                }
                if(!flag)
                {
                    result+=".";
                }
                flag=1;
                if(flag)
                {
                    count++;
                    record[dividend]=count;
                }
                dividend*=10;
            }
            int temp=dividend/denominator1;
            result+=to_string(temp);
            dividend=dividend-temp*denominator1;
        }
        int start=record[dividend];
        int end=count;
        if(result[0]=='.')
        {
            result="0"+result;
        }
        if(flag==1||flag==0)
        {
            return (minus==1)?"-"+result:result;
        }
        int j=0;
        while(result[j]!='.')
        {
            j++;
        }
        string s1=result.substr(0,j+start);
        string s2=result.substr(j+start,end-start+1);
        return (minus==1)?"-"+s1+"("+s2+")":s1+"("+s2+")";
    }
};


Problem solution in C.

unsigned int next(unsigned int p, unsigned int q) {
    return (p*10ull)%q;
}

char* fractionToDecimal(int numerator_, int denominator) {
    int si = 0;
    unsigned int q = denominator, numerator = numerator_;
    if (!numerator_) return "0";
    if (numerator_ < 0) numerator = -numerator_, si = 1-si;
    if (denominator < 0) q = -q, si = 1-si;
    unsigned int r0 = numerator % q;
    unsigned int r1 = next(r0, q);
    while (r0 != r1) {
        r0 = next(r0, q);
        r1 = next(r1, q);
        r1 = next(r1, q);
    }
    int clen = 0;
    if (r0) {
        do {
            r0 = next(r0, q); clen++;
        } while (r0 != r1);
    }
    r0 = numerator % q;
    r1 = clen ? r0 : 0;
    for (int i = 0; i < clen; i++) r1 = next(r1, q);
    int fralen = 0;
    while (r0 != r1) {
        fralen++;
        r0 = next(r0, q);
        r1 = next(r1, q);
    }
    char *s = (char *)malloc(20 + fralen + clen);
    int slen = 0;
    if (si) s[slen++] = '-';
    slen += sprintf(s+slen, "%u", numerator / q);
    r0 = numerator % q;
    if (r0 == 0) return s;
    s[slen++] = '.';
    for (int i = 0; i < fralen; i++) {
        s[slen++] = (r0 * 10ull)/q + '0';
        r0 = next(r0, q);
    }
    if (!clen) { s[slen++] = 0; return s; }
    s[slen++]='(';
    for (int i = 0; i < clen; i++) {
        s[slen++] = (r0 * 10ull)/q + '0';
        r0 = next(r0, q);
    }
    s[slen++]=')';
    s[slen++]=0;
    return s;
}


Post a Comment

0 Comments