Collapse to a Single Digit
EasyMath & GeometryFree
Problem
A barcode checker takes a non-negative integer n and keeps replacing it with the sum of its decimal digits until only one digit is left.
Return that final digit. Aim for a solution that does not loop over the digits at all.
Example 1
- Input:
- n = 38
- Output:
- 2
3 + 8 = 11, then 1 + 1 = 2, which is a single digit.
Example 2
- Input:
- n = 0
- Output:
- 0
Example 3
- Input:
- n = 123456789
- Output:
- 9
The digits add up to 45, and 4 + 5 = 9.
Constraints
- 0 ≤ n ≤ 10^15
Hint
Show the first hint
Simulate first: summing digits until one is left is easy. Now look at what stays the same at every step.
Walkthrough
How to approach it
01Clarify before coding
- Can n be 0? Yes, and the answer is 0: it is already a single digit.
- Is the input always non-negative? Yes, so there is no sign to handle.
- Is a loop acceptable? It works, but the interviewer asks for O(1), which hints at a closed formula.
02Brute force
Repeatedly split n into digits and add them until the value is below 10.
Cost: O(log n) per round and very few rounds (a 16-digit number sums to at most 144), so it is fast, but it misses the O(1) observation the question is testing.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.