Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The 'super digit' of a number is found by repeatedly summing its digits until one digit remains. The input is a string `n` conceptually repeated `k` times. The key insight: you never build the giant number — `superDigit(n, k) = superDigit(digitSum(n) · k)`, because summing the digits of the concatenation is just the digit-sum of one copy times k. Reduce that seed to a single digit (loop or recurse). Even better, the result is the digital root: `1 + (m − 1) mod 9` for `m > 0`. Time is O(|n|).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you avoid constructing the k-times-repeated string (which could be astronomically long) by recognising digitSum(repeat) = digitSum(n)·k, and whether you know the digital-root shortcut.
Where candidates slip
Building the string `n` repeated `k` times (memory blow-up), or reading `n` as an integer when it can be up to 10⁵ digits and overflow.
How to stand out
State the digit-sum-times-k collapse immediately, then mention the closed-form digital root `1 + (m−1) mod 9` as the O(1)-after-seed finish, and note it generalises 'casting out nines'.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewsuper digit of n repeated k timesBuild p literally?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Reduction — Sum Digits of the Seed Repeatedly
1Hint 1Explore hintHide hint
First collapse the k copies: `seed = digitSum(n) · k`. This avoids building the giant number.
2Hint 2Explore hintHide hint
Now reduce `seed` to one digit by the literal definition: while it has more than one digit, replace it with the sum of its digits.
3Hint 3Explore hintHide hint
Return the final single digit. The reduction loop runs only a few times because each pass shrinks the number drastically.
A · Core idea
Honor the recursive definition directly, but on the collapsed seed rather than the impossible full number.
Collapse first. The number p is n written k times. Its digit-sum is just every digit of n summed, k times over — i.e. k · digitSum(n). So set seed = digitSum(n) * k. We've replaced an O(|n|·k)-length number with a single integer at most 9 · |n| · k.
Reduce literally. Now apply the definition: while seed has more than one digit, sum its digits and repeat. For n = "148", k = 3: digitSum = 13, seed = 39, then 3 + 9 = 12, then 1 + 2 = 3. Return 3.
Why this is enough. Each reduction step replaces a number with its digit-sum, which is dramatically smaller (a 10-digit number drops to at most 90, then to at most 17, then to one digit), so the loop terminates in two or three passes regardless of input size. It's the straightforward, obviously-correct method; the closed-form below just collapses those last passes into one arithmetic expression.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = "9875", k = 4How to read it:digitSum collapses the k copies; each pass shrinks the number until a single digit remains.
8C · Code with teaching comments
Reference implementation previewpublic int superDigit(String n, int k) { long seed = 0; for (int i = 0; i < n.length(); i++) seed += n.charAt(i) - '0'; seed *= k; // k copies → multiply once while (seed >= 10) { // reduce to a single digitExplore the full codeHide the full code
D · Why it works and complexityO(|n| + log(seed)) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The only trick needed for correctness is the digitSum·k collapse — after that, the recursive definition is trivially cheap because digit-summing shrinks a number to roughly its logarithm each pass.
ComplexityO(|n| + log(seed)) time, O(1) space — Computing digitSum(n) scans the |n| characters once → O(|n|). The seed is at most 9·|n|·k, whose digit count is O(log(seed)); each reduction pass cuts it roughly to its digit-sum, converging in a handful of iterations. Constant extra space.
E · Edge cases and pitfalls3Building the string n repeated k times — memory blow-up of up to 10¹⁰ characters.Explore edge casesHide edge cases
Pitfalls
- Building the string n repeated k times — memory blow-up of up to 10¹⁰ characters.
- Using `int` for the seed in Java — 9·10⁵·10⁵ overflows 32 bits; use `long`.
- Reading n as a numeric type — it can be 10⁵ digits long.
Approach 2 of 2 · Optimal
Digital Root — Closed Form (Optimal)
1Hint 1Explore hintHide hint
Repeated digit-summing in base 10 is the digital root, and the digital root of m is congruent to m modulo 9.
2Hint 2Explore hintHide hint
The clean formula for m > 0 is `1 + (m − 1) mod 9` — it maps multiples of 9 to 9 (not 0) and everything else to its remainder.
3Hint 3Explore hintHide hint
Seed with `m = digitSum(n) · k`, then return `0 if m == 0 else 1 + (m − 1) % 9`. No reduction loop needed.
A · Core idea
Replace the reduction loop with the arithmetic identity behind it.
Why digit-summing = mod 9. A number and the sum of its digits leave the same remainder modulo 9, because 10 ≡ 1 (mod 9), so d_i · 10^i ≡ d_i (mod 9). Repeatedly digit-summing therefore preserves the value mod 9 and ends at the single digit congruent to it — that single digit is the digital root.
The off-by-one fix. Naively the digital root looks like m mod 9, but that maps multiples of 9 to 0, whereas the true digital root of, say, 18 is 9. The clean closed form 1 + (m − 1) mod 9 handles this: for m = 18, 1 + 17 mod 9 = 1 + 8 = 9; for m = 39, 1 + 38 mod 9 = 1 + 2 = 3. The only special case is m = 0, whose digital root is 0.
Apply to our seed. As before, m = digitSum(n) · k (the k-copy collapse). Then the answer is 0 if m == 0 else 1 + (m − 1) % 9. For n = "148", k = 3: m = 13·3 = 39, answer 1 + 38 % 9 = 1 + 2 = 3. For n = "9875", k = 4: m = 29·4 = 116, 1 + 115 % 9 = 1 + 7 = 8.
Why prefer it. It removes the reduction loop entirely, makes the divisibility-by-9 structure explicit, and is the canonical 'cast out nines' insight an interviewer is hoping you'll surface. The only real work is the single O(|n|) pass to compute digitSum(n).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = "148", k = 3Interactive diagram
Why digit-sum ≡ value mod 9
digitSum(n)Since 10 ≡ 1 (mod 9), each digit contributes itself mod 9 — repeated summing lands on the digital root.
3C · Code with teaching comments
D · Why it works and complexityO(|n|) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Repeated digit-sum is a thin disguise for 'value mod 9'. The digital root 1 + (m−1) mod 9 is the same identity that powers the casting-out-nines arithmetic check — once you see it, any 'reduce to one digit' problem is O(1) after the digit-sum.
ComplexityO(|n|) time, O(1) space — Summing the |n| digits is O(|n|); the multiply and the modulo are O(1). So the whole computation is O(|n|) time and O(1) space, independent of k.
E · Edge cases and pitfalls6n = "0", k = 5 — digitSum = 0, m = 0 → returns 0. The all-zero guard.Explore edge casesHide edge cases
Edge cases handled
n = "0", k = 5digitSum = 0, m = 0 → returns 0. The all-zero guard.n = "9", k = 1m = 9 → 1 + (9−1)%9 = 1 + 8 = 9. Multiples of 9 map to 9, not 0.n = "10", k = 1digitSum = 1, m = 1 → 1 + 0 = 1.
Pitfalls
- Using `m % 9` directly — gives 0 for multiples of 9 instead of 9.
- Forgetting the m == 0 guard, which would return 1 instead of 0.
- Overflowing a 32-bit int for the seed — multiply into a long.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int superDigit(String n, int k) { long m = 0; for (int i = 0; i < n.length(); i++) m += n.charAt(i) - '0'; m *= k; // collapse k copies if (m == 0) return 0;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Building the repeated string
n repeated k times can be 10¹⁰ characters — impossible to store. The digit-sum of k copies is just k times the digit-sum of one copy.
Explore the code comparisonHide the code comparison
Building the repeated string
n repeated k times can be 10¹⁰ characters — impossible to store. The digit-sum of k copies is just k times the digit-sum of one copy.
Don't write this
p = n * k # up to 10^10 chars — memory blow-up
seed = sum(int(d) for d in p)Write this instead
seed = sum(int(d) for d in n) * k # collapse without expanding2Wrong digital-root formula
`m % 9` returns 0 for any multiple of 9, but the digital root of 18 is 9. Use `1 + (m − 1) % 9` for m > 0.
Explore the code comparisonHide the code comparison
Wrong digital-root formula
`m % 9` returns 0 for any multiple of 9, but the digital root of 18 is 9. Use `1 + (m − 1) % 9` for m > 0.
Don't write this
return (int) (m % 9); // 18 → 0, should be 9Write this instead
return m == 0 ? 0 : (int) (1 + (m - 1) % 9);3Integer overflow on the seed
digitSum(n)·k can reach 9·10⁵·10⁵ ≈ 9·10¹⁰, which overflows a 32-bit int. Use a 64-bit type.
Explore the code comparisonHide the code comparison
Integer overflow on the seed
digitSum(n)·k can reach 9·10⁵·10⁵ ≈ 9·10¹⁰, which overflows a 32-bit int. Use a 64-bit type.
Don't write this
int seed = digitSum * k; // overflows for large n, kWrite this instead
long seed = (long) digitSum * k;Revise
Carry the pattern into the interview
Pattern to remember
Collapse k copies into digitSum(n)·k, then reduce to one digit (digital root)
Code pattern to memorize
def super_digit(n, k):
seed = sum(int(d) for d in n) * k # k copies → multiply once
while seed >= 10:
seed = sum(int(d) for d in str(seed))
return seed
# closed form: 1 + (seed - 1) % 9 (seed > 0)Rules to remember
- 1Never materialize the string repeated k times —
digitSum(n repeated k) = digitSum(n) · k. - 2Seed the reduction with
digitSum(n) · k, then keep summing digits until a single digit remains. - 3The super digit equals the digital root: for
m > 0,1 + (m − 1) mod 9(and 0 only when m = 0). - 4Parse
nas a string of digits — the original number can be huge (up to 10⁵ digits), so don't read it as an int. - 5One reduction pass after seeding is enough conceptually, but loop/recurse until
< 10to be safe.
Use this pattern when
- Repeated digit-sum / 'add the digits until one digit' problems
- Inputs too large to hold as a native integer (digit strings)
- Any 'cast out nines' / divisibility-by-9 reasoning
- Collapsing a k-fold repetition without expanding it
Choose another pattern when
- You need the full intermediate sums, not just the final digit → can't shortcut to digital root
- Digits are weighted (not a plain sum) → the ·k and mod-9 shortcuts break
- Base is not 10 → digital root uses (base − 1), adjust the modulus
- n fits comfortably in 64 bits and k = 1 → just sum digits directly, no machinery
Interview takeaway
Recursive Digit Sum is a digital-root problem dressed up with a k-fold repetition. The two insights — repetition multiplies the digit-sum by k, and repeated digit-summing is the digital root `1 + (m−1) mod 9` — turn a seemingly huge computation into O(|n|) work with no big integers.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternDigital-root reasoning: repeated digit-summing in base 10 preserves value mod 9, so the answer is `1 + (m−1) mod 9`. The k-fold repetition collapses to `digitSum(n)·k`, avoiding any big-number construction. This 'casting out nines' idea recurs wherever digits are summed to a fixed point.
Practice queueDirect variations and pattern siblings
Direct follow-ups