1351. Write the Fraction As a Decimal
Print a / b as a decimal. If the expansion repeats forever, wrap the
repeating part in parentheses.
1/2 -> 0.5
2/3 -> 0.(6)
1/6 -> 0.1(6)
1/7 -> 0.(142857)
4/333 -> 0.(012)
Long division, and the insight is about the REMAINDERS rather than the digits. At each step you multiply the remainder by 10, take a digit, and keep a new remainder. The state of the division is entirely the current remainder, so the moment a remainder repeats, every digit after it repeats too.
So record the position at which each remainder was first seen. When one comes back, the digits from that position onwards are the repeating block:
while remainder != 0 and remainder not seen before:
record seen[remainder] = current position
remainder = remainder * 10
emit digit remainder / b
remainder = remainder % b
A remainder of 0 ends the expansion exactly, with no parentheses.
Three details. The sign belongs to the whole result and is easiest applied once at the start, working with magnitudes afterwards. A result that is a whole number prints no decimal point at all. And detecting the repeat needs a map from remainder to POSITION, not merely a set, because the position is what says where the bracket opens.
Constraints - `-1000000 ≤ a ≤ 1000000` - `1 ≤ b ≤ 1000000`
Input
One line containing two integers a and b.
Output
Print a / b as a decimal, with any repeating part wrapped in parentheses.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.