C in 0ms, without using any container, and use 64bit int only when needed


  • 0
    K
    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;
    }

  • 0
    H

    Is your idea the Floyd cycle detection?


  • 0
    T

    You're not even using 64 bits at all... unsigned int and [signed] int are both 32 bits (usually), but you can use the extra 1 bit of sign to handle -2^31's overlflow, unlike in Java.

    Edit: I see the hidden ull now :)


Log in to reply
 

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