package algorithm

import "strconv"

// Problem Definition: https://leetcode.cn/problems/fraction-to-recurring-decimal/

func fractionToDecimal(numerator int, denominator int) string {
	if numerator%denominator == 0 {
		return strconv.Itoa(numerator / denominator)
	}

	var s []byte
	if numerator*denominator < 0 {
		s = append(s, '-')
	}

	numerator = abs(numerator)
	denominator = abs(denominator)
	integerPart := numerator / denominator
	s = append(s, strconv.Itoa(integerPart)...)
	s = append(s, '.')

	indexMap := make(map[int]int, 0)
	remainder := numerator % denominator
	for remainder != 0 && indexMap[remainder] == 0 {
		indexMap[remainder] = len(s)
		remainder *= 10
		s = append(s, '0'+byte(remainder/denominator))
		remainder %= denominator
	}

	if remainder > 0 {
		idx := indexMap[remainder]
		s = append(s[:idx], append([]byte{'('}, s[idx:]...)...)
		s = append(s, ')')
	}

	return string(s)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}