algorithms/leetcode/math/fractionToDecimal.go at master · TTWShell/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/* https://leetcode.com/problems/fraction-to-recurring-decimal/description/
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

    Given numerator = 1, denominator = 2, return "0.5".
    Given numerator = 2, denominator = 1, return "2".
    Given numerator = 2, denominator = 3, return "0.(6)".
*/

package lmath

import (
	"strconv"
	"strings"
)

func fractionToDecimal(numerator int, denominator int) string {
	res := []string{}
	if numerator*denominator < 0 {
		res = append(res, "-")
	}
	if numerator < 0 {
		numerator = -numerator
	}
	if denominator < 0 {
		denominator = -denominator
	}

	integer, fractional := numerator/denominator, numerator%denominator
	res = append(res, strconv.Itoa(integer))
	if fractional == 0 {
		return strings.Join(res, "")
	}

	res = append(res, ".")
	idx := len(res)
	maps := map[int]int{fractional: idx}
	idx++

	for ; fractional != 0; idx++ {
		res = append(res, strconv.Itoa(fractional*10/denominator))
		fractional = fractional * 10 % denominator
		if i, ok := maps[fractional]; ok {
			tmp := []string{}
			tmp = append(tmp, res[:i]...)
			tmp = append(tmp, "(")
			tmp = append(tmp, res[i:]...)
			tmp = append(tmp, ")")
			res = tmp
			break
		}
		maps[fractional] = idx
	}

	return strings.Join(res, "")
}