Abstract / Summary

Given a string of digits, add all the digits together and repeat until one digit remains.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 68% (80k+ submissions).

Typical patterns to solve this problem:

• Simulation
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The digitSum method implements a recursive reduction of a numeric string. It repeatedly partitions the input string into fixed-size blocks, computes the sum of the decimal digits within each block, concatenates those sums, and invokes itself on the resulting string. The recursion terminates when the length of the current string does not exceed the block size k. The final string is returned as the result.

Core Logic

The entry point checks whether the current string already satisfies the termination condition. If the length of s is less than or equal to k, the method returns s unchanged.

if len(s) <= k:
    return s

When the string is longer than k, a new accumulator next is created to collect the digit-sum results of each block. The method then enters a loop that processes the string from left to right.

next = ""
while s:
    x = s[:k]
    s = s[k:]

Inside the loop the first k characters are extracted into x, and the original string s is shortened by discarding those characters. The extracted block is converted to an integer, which removes any leading zeros and prepares the value for arithmetic digit extraction.

x = int(x)

The digit sum of the integer x is calculated using a classic modulo-division loop. The accumulator dsum starts at zero and is incremented by the remainder of x divided by ten. After each addition, x is reduced by integer division by ten, effectively shifting the decimal representation rightward.

dsum = 0
while x > 0:
    dsum += x % 10
    x //= 10

The computed digit sum dsum is converted back to a string and appended to the next accumulator. This concatenation builds the intermediate representation that will be fed into the next recursive call.

next += str(dsum)

When the outer while s loop finishes, all blocks have been processed and next holds the concatenated digit sums. The method then recurses with this new string.

return self.digitSum(next, k)

Edge Cases Handled

The implementation explicitly handles the situation where the input string length is already within the allowed block size. By returning the original string in that case, it avoids unnecessary processing and ensures that the recursion terminates correctly.

When a block contains leading zeros, converting the block to an integer discards those zeros before digit extraction. This behavior still yields the correct digit sum because the numeric value of the block is unchanged by leading zeros. The subsequent conversion of the sum back to a string reintroduces any necessary digits without preserving the original leading zeros, which aligns with the intended reduction semantics.

The loop condition while s: guarantees that the algorithm does not attempt to process an empty string. Since the string is shortened by exact k-character slices each iteration, the loop naturally terminates when all characters have been consumed.

Performance Optimizations

The digit-sum calculation uses pure integer arithmetic rather than converting the block to a list of characters and iterating over them. This approach reduces the overhead of character handling and leverages fast CPU integer operations.

By processing the input string in place-slicing off the leading k characters and reassigning s-the algorithm avoids creating additional intermediate collections for the entire set of blocks. Only the accumulator next grows proportionally to the number of blocks, which is necessary for the recursive step.

The recursion depth is bounded by the number of times the string length can be reduced below k. Each recursive call works on a strictly shorter string, ensuring that the call stack grows only as needed for the reduction process. This design eliminates the need for auxiliary data structures to track intermediate states.

Think of this code like a machine that likes to shrink long strings of numbers. First, the machine checks if the string is already small enough. If the string is short, it just says that it is finished.

If the string is still too long, the machine starts chopping it up into little bite-sized pieces. Each piece has a specific length that we choose. For every little piece, the machine takes all the numbers inside and adds them together to make a brand new, smaller number.

After it adds all the pieces together, it joins those new numbers into a fresh string. Because that new string might still be too long, the machine takes the whole thing and starts the process again from the beginning. It keeps chopping, adding, and building until the final string is finally short enough to stop.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python			TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++	JS	Java		Python	Go	Rust	TS
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem				Ruby
	fsq	C++
	JoshCrozier		JS
	lkwq007					Python
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality