Error case found numerator=1 and denominator=2148728 in C


  • 0

    In my case, I tried to use C to realise this function and took fixed size of char array to store the result in the very beginning and then as usual I will try to use realloc to dynamically allocate the space for the array for portability. But when the size is 2000, the code accepted, but, but when I input my own test case 1 and 2148728, it failed as I have expected -> the size will be much larger and I have to adjust the size to 5000 to get passed. So there is definitely a bug in testing cases;

    one more thing, I cannot use realloc to dynamically allocate space in this function - reason unknown till now.


    #define LEN 2000 
    struct MyListNode
    {
        long long key;
        int val;
        struct MyListNode *next;
    };
    
    void push(struct MyListNode* head, long long key, int val)
    {
        struct MyListNode *p = head;
        while(p->next)
            p = p->next;
        struct MyListNode *t = (struct MyListNode*)malloc(sizeof(struct MyListNode));
        t->key = key;
        t->val = val;
        p->next = t;
    }
    
    int pop(struct MyListNode* head, long long key)
    {
        struct MyListNode *p = head->next;
        while(p)
        {
            if(p->key == key)
                return p->val;
            p = p->next;
        }
        return 0;
    }
    char* fractionToDecimal(int n, int d)
    {
        if(n == 0) return "0";
        char *s = (char*)malloc(sizeof(char)*LEN);
        int index = 0;
        if((n<0 && d>0) || (n>0 && d<0)) s[index++] = '-'; //get the sign part;
        long long numerator = (n==INT_MIN)? -1*(long long)n : abs(n);
        long long denominator = (d==INT_MIN)? -1*(long long)d : abs(d);
        long long integer = numerator/denominator; //collecting the integer part;
        if(integer == 0)
            s[index++] = '0';
        else
        {
            char *t = (char*)malloc(sizeof(char)*20); //used to store the integer part in reverse order;
            int index0 = 0;
            while(integer)
            {
                t[index0++] = integer%10+'0';
                integer /= 10;
            }
            for(int i = index0-1; i > -1; i--) //reverse it again, then s will store the integer part in normal sequence;
                s[index++] = t[i];
        }
        long long remainder = numerator%denominator; //get the remainder by mod operator;
        if(remainder == 0) 
        {
            s[index] = '\0';
            return s;
        }
        s[index++] = '.'; //there are decimals;
        struct MyListNode *head = (struct MyListNode*)malloc(sizeof(struct MyListNode)); //used to store the remainder digit index in string for recurring;
        while(remainder)
        {
            int pre = pop(head, remainder);
            if(pre) //check if this digit has already occurred, if so, add brackets;
            {
                for(int i = index; i > pre; i--)
                    s[i] = s[i-1];
                index++;
                s[pre] = '(';
                s[index++] = ')';
                break;
            }
            push(head, remainder, index);
            remainder *= 10; //imitating division process here, retrieving the high decimal digit;
            s[index++] = remainder/denominator+'0';
            remainder %= denominator;
        }
        s[index] = '\0';
        return s;
    }

Log in to reply
 

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