Digital Root

Given a non-negative integer n, repeatedly replace n by the sum of its decimal digits until only a single digit remains. Print that final single digit, known as the digital root of n.

Input: A single line containing one non-negative integer n. Output: Print the single-digit digital root of n.

0 <= n <= 10^18

The formula's edge case (digital root of 0 is defined as 0, not falling out of the '1 + ... mod 9' pattern) needs explicit handling - a clean example of a mathematical formula needing one special-cased boundary condition.

Repeatedly sum a number's digits until only a single digit remains. Brute force: The direct simulation (repeatedly summing digits until one remains) is itself a perfectly valid approach and not really 'brute force' in a bad sense - it's simple and correct, just not O(1). Optimised: The digital root has a well-known mathematical connection to modular arithmetic base 9 (since digit-sum operations preserve a number's value modulo 9) - this lets the ENTIRE repeated-summing process collapse into a single O(1) formula, 1 + (n-1) mod 9, without ever actually summing any digits.

1. The DIRECT simulation approach: sum the digits, and if the result still has more than one digit, sum ITS digits again, repeating until a single digit remains. 2. There's also a well-known O(1) FORMULA: for n > 0, the digital root equals 1 + (n - 1) mod 9; the digital root of 0 is defined as 0. 3. Double-check the formula against multiples of 9 (it should always give 9, never 0, for any positive multiple of 9).

Time: O(1) with the formula; O(log n) per summing pass with the direct simulation (and typically very few passes needed in practice). Space: O(1) either way.

n=0 has digital root 0. Numbers that are already single digits (1-9) are their own digital root. n can be as large as 10^18, so read it as a 64-bit integer.

Be ready to derive or at least justify the 1 + (n-1) mod 9 formula's connection to modular arithmetic - simply stating the formula without explaining WHY it works is less impressive than connecting it to the 'digit sum preserves value mod 9' fact.