Clock drift readout

A workshop wants a pendulum clock's drift per day written out exactly — no rounding, no ellipsis. Most such figures never terminate, so the readout must mark the part that repeats.

The problem

A clock is set against a reference at the start of a trial and read again at the end. Over days whole days it has gained seconds seconds; a clock that loses time reports a negative figure. The certificate prints that drift per day as an exact decimal.

Return that decimal as a string. If the division terminates, print the digits and stop. Otherwise it repeats forever, as every non-terminating decimal of a fraction does: print the repeating block once, in parentheses. Print a whole number with no point at all, and no trailing zeros. Zero drift prints as 0.

Input. seconds — an integer, the total drift, possibly negative or zero. days — an integer, the length of the trial in days, at least 1.

Output. A string: the exact value of seconds / days, any repeating block in parentheses.

Example.

seconds = 7,  days = 8    ->  "0.875"
seconds = 5,  days = 3    ->  "1.(6)"

Seven eighths terminates after three digits. Five thirds is 1.6666…, so 6 repeats from the first decimal place.

A second example, where the repeat starts partway through and the drift is negative:

seconds = -7, days = 12   ->  "-0.58(3)"

Seven twelfths is 0.58333…: 5 and 8 happen once, then 3 repeats, and the sign sits out front.

Constraints.

• -10^9 <= seconds <= 10^9
• 1 <= days <= 10^4
• The repeating block is shorter than days.

Hints

Approach

Brute force

Generate digits with long division and detect the repeat by comparing suffixes of the digit string: O(d²) character comparisons for d digits, and it declares a repeat too early, since 0.121212… and 0.1212125… agree for a while.

The insight

A remainder is the entire state of long division, so the decimal repeats from the moment a remainder appears for the second time.

Each step computes digit = rem * 10 // days and rem = rem * 10 % days. Only rem survives the step, so two steps with the same remainder produce identical digits from then on. There are at most days distinct remainders, so either a remainder reaches 0 — the decimal terminates — or one repeats within days steps. A map from remainder to digit position turns detection into one lookup.

Algorithm

1. If seconds is 0, return "0". Otherwise note the sign and take absolute values.
2. Emit the integer part n // d and set rem = n % d. If rem is 0, stop.
3. If rem is already in the map, insert ( at its recorded position, append ), and stop.
4. Record rem at the current digit position; set rem *= 10, append the digit rem // d, set rem %= d, and go back to step 3.
5. A rem of 0 terminates the decimal: stop with no brackets.
6. Join sign, integer part, . and the fraction.

Complexity

Time O(days) — one digit per turn, and the loop cannot outrun the distinct remainders. Space O(days) — one map entry and one digit per step.

Solution

"""Clock drift readout — long division, with a map from remainder to digit position."""


def solve(seconds, days):
    if seconds == 0:
        return "0"
    sign = "-" if seconds < 0 else ""
    n, d = abs(seconds), abs(days)
    whole, rem = divmod(n, d)        # sign stripped first: floor division on negatives lies
    if rem == 0:
        return sign + str(whole)

    digits = []
    first_at = {}                    # remainder -> index in `digits` where its digit lands
    while rem != 0 and rem not in first_at:
        # invariant: `rem` is the whole state of the division, so a repeat of rem
        # means every digit from here on repeats too.
        first_at[rem] = len(digits)
        rem *= 10
        digits.append(str(rem // d))
        rem %= d

    if rem == 0:
        fraction = "".join(digits)
    else:
        start = first_at[rem]
        fraction = "".join(digits[:start]) + "(" + "".join(digits[start:]) + ")"
    return sign + str(whole) + "." + fraction

TESTS = [
    ((7, 8), "0.875"),
    ((5, 3), "1.(6)"),
    ((-7, 12), "-0.58(3)"),
    ((0, 9), "0"),
    ((9, 3), "3"),
    ((1, 7), "0.(142857)"),
    ((-4, 2), "-2"),
    ((1, 6), "0.1(6)"),
]

Pitfalls

• Dividing negatives directly. In Python -7 // 12 is -1 and -7 % 12 is 5, so the readout comes out as -1.41(6). Strip the sign first and prepend - at the end.
• Recording the remainder after its digit. The bracket opens in the wrong place: -7 / 12 prints -0.5(83), not -0.58(3).
• Treating a remainder of 0 as a repeat. Stored in the map like any other, it makes 7 / 8 print 0.875(0).
• Returning "-0" for a zero drift, or "1." for a whole number.

Variants

• Reserve turnstile — a first-position map again, over running balances instead of remainders.
• What a hash map buys you — the lesson on a map as a memory of states already visited.