Fraction as a Repeating Decimal
Problem
Given an integer numerator and a non-zero integer denominator, return the value of the fraction as a decimal string. If the digits after the point repeat forever, wrap the repeating block in parentheses. Either number may be negative, and the result carries a minus sign only when the value itself is negative.
Examples
Input: num = 1, den = 6
Output: "0.1(6)"
Why: 1/6 = 0.1666..., the 6 repeats after one digit that does notInput: num = 22, den = 7
Output: "3.(142857)"Input: num = -50, den = 8
Output: "-6.25"
Why: edge case, a negative value whose digits stopHints
0 / 3
Do the long division you learned at school by hand for 1 divided by 6 and watch what you carry from one step to the next.
Each new digit depends only on the current remainder, and a remainder is always smaller than the denominator. Once a remainder comes back, every digit after it repeats.
Handle the sign and the whole part first. Then, while the remainder is not zero, remember the position where each remainder first appeared, multiply it by ten, emit the quotient digit and keep the new remainder. If a remainder repeats, insert the opening parenthesis at its remembered position.
Solution
After the whole part is written, long division is a machine whose entire state is the current remainder: multiply by ten, emit the quotient digit, keep the new remainder. There are fewer than den possible remainders, so either one of them becomes zero and the decimal ends, or one of them appears a second time and from then on the same digits come out in the same order. A dictionary from remainder to the index of the digit it produced tells exactly where the repeating block starts. Time and space are O(den) in the worst case, since that bounds the number of distinct remainders.
def to_decimal(num, den):
if num == 0:
return "0"
sign = "-" if (num < 0) != (den < 0) else ""
num, den = abs(num), abs(den)
whole, rem = divmod(num, den)
digits, seen = [], {}
while rem and rem not in seen:
seen[rem] = len(digits) # where this remainder started
rem *= 10
digits.append(str(rem // den))
rem %= den
frac = "".join(digits)
if rem: # a remainder came back: cycle
i = seen[rem]
frac = frac[:i] + "(" + frac[i:] + ")"
return sign + str(whole) + ("." + frac if frac else "")
print(to_decimal(1, 6)) # -> 0.1(6)
print(to_decimal(22, 7)) # -> 3.(142857)
print(to_decimal(-50, 8)) # -> -6.25
print(to_decimal(4, 2)) # -> 2
print(to_decimal(1, 333)) # -> 0.(003)Stuck on the idea rather than the code? Modular Arithmetic covers it.