LeetCode //C - 166. Fraction to Recurring Decimal

166. Fraction to Recurring Decimal

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.
 

Example 1:

Input: numerator = 1, denominator = 2
Output: “0.5”

Example 2:

Input: numerator = 2, denominator = 1
Output: “2”

Example 3:

Input: numerator = 4, denominator = 333
Output: “0.(012)”

Constraints:

• $-2^{31}<=numerator,denominator<=2^{31}-1$
• denominator != 0

From: LeetCode
Link: 166. Fraction to Recurring Decimal

---

Solution:

Ideas:

1. Dynamic Buffer Resizing: Instead of using a fixed-size buffer, we dynamically resize the result buffer if needed. This prevents buffer overflows and manages memory more effectively.
2. Initial Allocation and Reallocation: The result buffer is initially allocated with a reasonable size and is reallocated dynamically to accommodate larger strings.
3. Proper Null Termination: Ensure the result string is properly null-terminated after inserting parentheses.

Code:

typedef struct {
    long long remainder;
    int position;
    struct ListNode* next;
} ListNode;

// Function to create a new node
ListNode* createNode(long long remainder, int position) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->remainder = remainder;
    newNode->position = position;
    newNode->next = NULL;
    return newNode;
}

// Function to find a node with a given remainder
int findPosition(ListNode* head, long long remainder) {
    ListNode* current = head;
    while (current) {
        if (current->remainder == remainder) {
            return current->position;
        }
        current = current->next;
    }
    return -1;
}

// Function to add a node to the linked list
void addNode(ListNode** head, long long remainder, int position) {
    ListNode* newNode = createNode(remainder, position);
    newNode->next = *head;
    *head = newNode;
}

// Function to free the linked list
void freeList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        free(temp);
    }
}

// Function to return the fraction in string format
char* fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) {
        char* result = (char*)malloc(2 * sizeof(char));
        strcpy(result, "0");
        return result;
    }

    // Allocate an initial result buffer with a reasonable size
    int initialSize = 64;
    int currentSize = initialSize;
    char* result = (char*)malloc(currentSize * sizeof(char));
    if (!result) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
    memset(result, 0, currentSize);
    int resultIndex = 0;

    // Handle negative numbers
    if ((numerator < 0) ^ (denominator < 0)) {
        result[resultIndex++] = '-';
    }

    long long num = llabs((long long)numerator);
    long long den = llabs((long long)denominator);

    // Append integer part
    int intPartLength = snprintf(result + resultIndex, currentSize - resultIndex, "%lld", num / den);
    resultIndex += intPartLength;

    long long remainder = num % den;
    if (remainder == 0) {
        return result;
    }

    // Append the decimal point
    result[resultIndex++] = '.';

    // Create a linked list to track remainders
    ListNode* remainderMap = NULL;

    while (remainder != 0) {
        // Check if the result buffer needs to be enlarged
        if (resultIndex + 2 >= currentSize) {
            currentSize *= 2;
            result = (char*)realloc(result, currentSize * sizeof(char));
            if (!result) {
                fprintf(stderr, "Memory reallocation failed\n");
                exit(1);
            }
        }

        int existingPos = findPosition(remainderMap, remainder);
        if (existingPos != -1) {
            // Insert parentheses
            int len = strlen(result);
            for (int i = len; i >= existingPos; --i) {
                result[i + 1] = result[i];
            }
            result[existingPos] = '(';
            result[len + 1] = ')';
            result[len + 2] = '\0';
            freeList(remainderMap);
            return result;
        }

        addNode(&remainderMap, remainder, resultIndex);

        remainder *= 10;
        int digitLength = snprintf(result + resultIndex, currentSize - resultIndex, "%lld", remainder / den);
        resultIndex += digitLength;
        remainder %= den;
    }

    freeList(remainderMap);
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121