aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-23 22:57:45 -0600
committerJack Sangdahl <[email protected]>2025-09-23 22:57:45 -0600
commitff0500a7e8c426a0a6f46076761869fc88098d87 (patch)
tree744b345c338c8cffb2acd7ed4e587e25531484f1
parent5e2e4726603b20bc5a876e308807c3bf97f37776 (diff)
downloadleetcode-ff0500a7e8c426a0a6f46076761869fc88098d87.tar.gz
leetcode-ff0500a7e8c426a0a6f46076761869fc88098d87.zip
166. fraction to recurring decimal
-rw-r--r--fraction_to_recurring_decimal.c92
-rw-r--r--fraction_to_recurring_decimal.py36
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))