leetcode

// 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);
}