Sum of Digits in Base K

LeetCode 1837. Sum of Digits in Base K gives you two integers, n and k, and asks you to return the sum of the digits of n when represented in base k.

For example, n = 34 in base 6 is "54" (because 5 x 6 + 4 = 34). The digit sum is 5 + 4 = 9.

Why this problem matters

This problem isolates the "extract digits of a number in a given base" pattern. You have probably done this in base 10 many times: take the last digit with n % 10, remove it with n // 10, and repeat. Base K is the exact same loop with 10 replaced by k. Once you internalize that base conversion is just repeated division, you can apply it to any base.

This pattern shows up whenever you need to work with digits in non-decimal bases, convert between numeral systems, or solve problems involving digital roots and digit sums.

The approach

You do not need to build the full base-K string. You only need the digits, and you can sum them as you extract them.

The algorithm:

1. Initialize a running sum to 0.
2. While n is greater than 0, take n % k to get the current digit, add it to the sum, and set n = n // k to remove that digit.
3. Return the sum.

This works because n % k gives you the least significant digit in base k, and n // k shifts the number right by one position in that base. You are peeling off digits from right to left and accumulating their sum.

def sum_base(n: int, k: int) -> int:
    result = 0
    while n > 0:
        result += n % k
        n //= k
    return result

That is the entire solution. Three lines inside the function. No string conversion, no array allocation, just arithmetic.

Visual walkthrough

Let's trace through n = 34, k = 6 step by step. Watch how each iteration peels off one base-6 digit and adds it to the running total.

Two iterations and we are done. The loop runs once per digit in the base-K representation, which is at most log_k(n) + 1 times.

Why not convert to a string?

You could convert n to its base-K string representation and then sum the character values. But that allocates a string you do not need. The modular arithmetic approach is both simpler and more efficient. It also mirrors the digit extraction pattern you will use in dozens of other problems, so practicing it here pays dividends later.

Complexity analysis

Time is O(log_k(n)) because the number of digits in the base-K representation of n is floor(log_k(n)) + 1. Each iteration does constant work.

Space is O(1). You only store the running sum and modify n in place. No extra data structures needed.

Building blocks

1. Digit extraction via modular arithmetic

The core pattern of pulling digits from a number one at a time:

while n > 0:
    digit = n % base
    n //= base

This works in any base. In base 10, you get decimal digits. In base 2, you get bits. In base 16, you get hex digits. The pattern is identical every time. You will see it in problems like "Happy Number" (summing squares of digits), "Add Digits" (digital root), "Reverse Integer," and "Palindrome Number."

2. Accumulating while extracting

Instead of collecting digits into a list and then processing them, you process each digit the moment you extract it. This is a common optimization that drops space from O(log n) to O(1). Here you add each digit to a sum, but the same idea works for building a reversed number, checking palindrome properties, or computing any aggregate over digits.

result = 0
while n > 0:
    result += n % k
    n //= k

Edge cases

• n = 1, any valid k: The base-K representation of 1 is always "1". The digit sum is 1.
• n is less than k: The number is already a single digit in base K. The loop runs once and returns n itself.
• k = 2 (binary): The digit sum equals the number of 1-bits in n (the Hamming weight / popcount).
• k = 10 (decimal): Reduces to the classic "sum of digits" problem you have likely seen before.
• Large n, small k: More digits to extract, but the loop still runs in O(log_k(n)) time.

From understanding to recall

You have seen that base conversion is just repeated % k and // k. The code is short and the logic is clean. But under interview pressure, even simple patterns can slip if you have not practiced them recently.

The details matter: do you use % or // first? Do you check n > 0 or n >= 0? Is the result initialized to 0 or something else? These are not conceptual questions. They are recall questions, and spaced repetition is how you make the answers automatic.

CodeBricks breaks this problem into its digit extraction building block and drills it at increasing intervals. After a few rounds, the while n > 0: digit = n % k; n //= k loop flows out without hesitation. When you see any digit manipulation problem, you do not think about it. You just write it.

Related posts

• Happy Number - Uses digit extraction to compute the sum of squared digits, the same modular arithmetic loop applied in a cycle detection context
• Add Digits - Repeatedly sums digits until a single digit remains, the same digit extraction pattern taken to its mathematical conclusion
• Palindrome Number - Reverses half of a number's digits using the same % 10 and // 10 extraction loop