Sponsored
Sponsored
This method utilizes long division to compute the fraction part. We keep track of the remainder at each step using a hash map (or dictionary), which maps the remainder to its corresponding position in the decimal.
If a remainder repeats, it means the decimals will start repeating onwards, and we enclose the repeating sequence in parentheses.
Time Complexity: O(d), where d is the length of the repeating sequence in the worst case. This is because each fractional digit is calculated one at a time.
Space Complexity: O(d), for storing seen remainders in the hash map.
1#include <string.h>
2#include <stdio.h>
3#include <stdlib.h>
4
5char* fractionToDecimal(int numerator, int denominator) {
6 if (numerator == 0) return "0";
7
8 char* result = malloc(10000);
9 int index = 0;
10 if ((numerator < 0) ^ (denominator < 0)) {
11 result[index++] = '-';
12 }
13
14 // Convert to long long to avoid overflow
15 long long num = llabs(numerator);
16 long long den = llabs(denominator);
17 index += sprintf(result+index, "%lld", num / den);
18 long long remainder = num % den;
19 if (remainder == 0) {
20 result[index] = '\0';
21 return result;
22 }
23
24 result[index++] = '.';
25 int* map = calloc(den, sizeof(int));
26 memset(map, -1, den * sizeof(int));
27
28 while (remainder != 0) {
29 if (map[remainder] != -1) {
30 int pos = map[remainder];
31 memmove(result + pos + 1, result + pos, index - pos);
32 result[pos] = '(';
33 result[index + 1] = ')';
34 result[index + 2] = '\0';
35 free(map);
36 return result;
37 }
38
39 map[remainder] = index;
40 remainder *= 10;
41 index += sprintf(result+index, "%lld", remainder / den);
42 remainder %= den;
43 }
44 result[index] = '\0';
45 free(map);
46 return result;
47}The C solution uses manual memory management functions like malloc to allocate space for the result. It tracks the remainders using an array, indexed by the current remainder value. If the same remainder appears again, the repeating sequence is detected, and parentheses are inserted using memmove.
Special care is taken with long long to avoid overflow issues when calculating the absolute values.