InterviewBit – Fraction

Source: InterviewBit – Fraction

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.

Example :

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

---

解題：

1. 這一題因為題目沒有給定數值的範圍大小，如面試時遇到應先確認數值範圍，評估如遇到無法除盡且過一定時間仍找不到小數點後位數重複機制之情況下是否要設置檢查點進行跳出迴圈，另外也須確認輸入值是否可為負數；
2. 對釋例的前兩個狀況與最後一個狀況相較之下非常簡單，只要不斷進行小數點位數推進直到餘數為零即可。
3. 針對最後一個狀況，須運用一個概念：在小數點位數推進時，如遇到已在先前推進時遭遇之相同餘數值，代表後續之數值必定相同。舉例如下：

   A = 2, B = 3
   2 % 3 = 2
   小數點後第一位數值 = 20 // 3 = 6
   餘數 = 20 % 3 = 2
   與先前取餘值相同，故小數點後第二位數值必與第一位數值相同；
   
   A = 2, B = 7
   2 % 7 = 2
   decimal_1 = 20 // 7 = 2
   modular = 20 % 7 = 6
   decimal_2 = 60 // 7 = 8
   modular = 60 % 7 = 4
   decimal_3 = 40 // 7 = 5
   modular = 40 % 7 = 5
   decimal_4 = 50 // 7 = 7
   modular = 50 % 7 = 1
   decimal_5 = 10 // 7 = 1
   modular = 1- % 7 = 3
   decimal_6 = 30 // 7 = 4
   modular = 30 % 7 = 2
   此時餘數已與計算小數點後第一位時使用之餘數相同
   此時便可確定小數點後第 7, 8, 9......位均為前 6 位數之重複

   而要確認是否遇到重複的取餘值，最輕鬆快速的方式自然是建立一個 hashmap 記錄所有已遇到的餘數值；

4. 在進行餘數值記錄的同時，須注意因重複的狀況並不一定從小數點後第一位開始，故在推進時亦必須記錄相關餘數所代表之小數點後索引值，以確保輸出時找得到括弧的放置點。

Code:

from collections import defaultdict
class Solution:
	# @param A : integer
	# @param B : integer
	# @return a strings
    def fractionToDecimal(self, A, B):
        if A % B == 0: return str(A//B)
        neg = False
        if (A<0 or B<0) and not (A<0 and B<0): 
            neg = True
            A, B = abs(A), abs(B)
        intstr = str(A//B)
        modularDict = defaultdict(bool)
        modularIdx, decimalIdx = {}, 0
        modular = A%B
        decimals = []
        while modularDict[modular] == False and modular != 0:
            modularDict[modular] = True
            modularIdx[modular] = decimalIdx
            decimalIdx += 1
            modular *= 10
            decimals.append(str(modular//B))
            modular = modular % B
        if modularDict[modular]:
            #divide into before and in the brackets
            beforeBra = "".join(decimals[:modularIdx[modular]])
            inBra = "("+"".join(
                           decimals[modularIdx[modular]:])+")"
            decimals = [beforeBra, inBra]
        if neg:
            return "-"+intstr+"."+"".join(decimals)
        return intstr+"."+"".join(decimals)

GitHub: GitHub