diff options
author | Jack Sangdahl <[email protected]> | 2025-09-23 22:57:45 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-23 22:57:45 -0600 |
commit | ff0500a7e8c426a0a6f46076761869fc88098d87 (patch) | |
tree | 744b345c338c8cffb2acd7ed4e587e25531484f1 | |
parent | 5e2e4726603b20bc5a876e308807c3bf97f37776 (diff) | |
download | leetcode-ff0500a7e8c426a0a6f46076761869fc88098d87.tar.gz leetcode-ff0500a7e8c426a0a6f46076761869fc88098d87.zip |
166. fraction to recurring decimal
-rw-r--r-- | fraction_to_recurring_decimal.c | 92 | ||||
-rw-r--r-- | fraction_to_recurring_decimal.py | 36 |
2 files changed, 128 insertions, 0 deletions
diff --git a/fraction_to_recurring_decimal.c b/fraction_to_recurring_decimal.c new file mode 100644 index 0000000..c713c29 --- /dev/null +++ b/fraction_to_recurring_decimal.c @@ -0,0 +1,92 @@ +// 166. Fraction to Recurring Decimal +#include "leetcode.h" + +/* + * given two integers representing the 'numerator' and 'denominator' of a + * fraction, reeturn 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 10^4 for all the digits given inputs. + */ + +struct visited { + long key; + int idx; + UT_hash_handle hh; +}; + +char *fractionToDecimal(int numerator, int denominator) { + if (!numerator) { + char *ans = (char *)malloc(2 * sizeof(char)); + ans[0] = '0'; + ans[1] = '\0'; + return ans; + } + char *ans = (char *)malloc(10001 * sizeof(char)); + long n = numerator, d = denominator; + int idx = 0, sign = n / labs(n) * d / labs(d); + if (sign == -1) + ans[idx++] = '-'; + n = labs(n); + d = labs(d); + long curr = n / d; + n = 10 * (n - curr * d); + if (curr) { + char buffer[10]; + int buffer_idx = 0; + while (curr) { + int digit = curr - curr / 10 * 10; + buffer[buffer_idx++] = '0' + digit; + curr /= 10; + } + for (int i = buffer_idx - 1; i >= 0; --i) + ans[idx++] = buffer[i]; + } else + ans[idx++] = '0'; + if (!n) { + ans[idx] = '\0'; + return ans; + } + ans[idx++] = '.'; + struct visited *hash_map = NULL; + while (true) { + if (!n) + break; + struct visited *node = NULL; + HASH_FIND(hh, hash_map, &n, sizeof(long), node); + if (node) { + ans[idx++] = ')'; + int rep_start_idx = node->idx; + for (int i = idx++ - 1; i >= rep_start_idx; --i) + ans[i + 1] = ans[i]; + ans[rep_start_idx] = '('; + break; + } else { + node = (struct visited *)malloc(sizeof(struct visited)); + node->key = n; + HASH_ADD(hh, hash_map, key, sizeof(long), node); + curr = n / d; + n = 10 * (n - curr * d); + ans[idx++] = '0' + curr; + } + } + struct visited *del, *tmp; + HASH_ITER(hh, hash_map, del, tmp) { + HASH_DEL(hash_map, del); + free(del); + } + ans[idx] = '\0'; + return ans; +} + +int main() { + char *ftd1 = fractionToDecimal(1, 2); + char *ftd2 = fractionToDecimal(2, 1); + char *ftd3 = fractionToDecimal(4, 333); + printf("%s\n", ftd1); // expect: 0.5 + printf("%s\n", ftd2); // expect: 2 + printf("%s\n", ftd3); // expect: 0.(012) + free(ftd1); + free(ftd2); + free(ftd3); +} diff --git a/fraction_to_recurring_decimal.py b/fraction_to_recurring_decimal.py new file mode 100644 index 0000000..e77819c --- /dev/null +++ b/fraction_to_recurring_decimal.py @@ -0,0 +1,36 @@ +# 166. Fraction to Recurring Decimal + +""" +given two integers representing the 'numerator' and 'denominator' of a +fraction, reeturn 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 10^4 for all the digits given inputs. +""" + + +class Solution(object): + def fractionToDecimal(self, numerator, denominator): + """ + :type numerator: int + :type denominator: int + :rtype: str + """ + n, rem = divmod(abs(numerator), abs(denominator)) + sign = "-" if numerator * denominator < 0 else "" + ans, stack = [sign + str(n), "."], [] + while rem not in stack: + stack.append(rem) + n, rem = divmod(rem * 10, abs(denominator)) + ans.append(str(n)) + idx = stack.index(rem) + ans.insert(idx + 2, "(") + ans.append(")") + return "".join(ans).replace("(0)", "").rstrip(".") + + +if __name__ == "__main__": + obj = Solution() + print(obj.fractionToDecimal(1, 2)) + print(obj.fractionToDecimal(2, 1)) + print(obj.fractionToDecimal(4, 333)) |