LeetCode 1837 - Sum of Digits in Base K

LeetCode Problem 1837

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem is asking us to convert a given integer n from base 10 into another base k, then compute the sum of its digits in that base. For example, if n is 34 and k is 6, first we convert 34 into base 6, which yields 54, and then sum the digits: 5 + 4 = 9.

The inputs are constrained such that 1 <= n <= 100 and 2 <= k <= 10. This tells us that n is small and the base is within a simple single-digit range, so performance is not a major concern. We are guaranteed valid, small inputs, so we do not need to handle negative numbers, zero, or invalid bases.

Important edge cases include when n is already less than k, in which case its base k representation is a single digit equal to n, and when k equals 10, meaning no conversion is needed.

The output is always a single integer representing the sum of digits in base 10 after conversion.

Approaches

The brute-force approach is straightforward: convert n to a string representing its digits in base k, iterate through each character, convert it back to an integer, and sum the digits. This approach works because converting to another base and summing digits is a direct calculation. Given the small input constraints, this approach would be fast enough.

A more optimal and elegant approach uses a mathematical technique without constructing a string. Repeatedly take the remainder of n divided by k (n % k) to get the least significant digit in base k, add it to a running sum, and then integer-divide n by k (n //= k). Continue until n becomes zero. This avoids string conversion and is more memory efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(log_k n)	O(log_k n)	Convert to string in base k and sum digits
Optimal	O(log_k n)	O(1)	Use repeated division and remainder to sum digits directly

Algorithm Walkthrough

1. Initialize a variable total to 0 to keep track of the sum of digits.
2. While n is greater than 0:

a. Compute digit = n % k to get the current least significant digit in base k.

b. Add digit to total.

c. Update n using integer division n //= k to remove the digit we just processed. 3. When the loop ends, total contains the sum of digits of n in base k. Return total.

Why it works: This approach works because taking the remainder with k always produces the correct least significant digit in base k, and integer division shifts the number to the right in base k. Repeating this process until n becomes zero ensures all digits are processed exactly once, and their sum is computed.

Python Solution

class Solution:
    def sumBase(self, n: int, k: int) -> int:
        total = 0
        while n > 0:
            total += n % k
            n //= k
        return total

The Python implementation follows the optimal approach described above. We initialize total to accumulate the sum. Each iteration of the loop extracts the least significant digit of n in base k using the modulus operator, adds it to total, and removes it from n using integer division. The loop ends when n becomes zero, at which point total contains the final sum.

Go Solution

func sumBase(n int, k int) int {
    total := 0
    for n > 0 {
        total += n % k
        n /= k
    }
    return total
}

The Go implementation mirrors the Python solution. The main differences are syntax-related: we use for instead of while, and /= performs integer division in Go for integers. No additional memory structures are required.

Worked Examples

Example 1: n = 34, k = 6

Step	n	n % k	total	n // k
1	34	4	4	5
2	5	5	9	0

Result: 9

Example 2: n = 10, k = 10

Step	n	n % k	total	n // k
1	10	0	0	1
2	1	1	1	0

Result: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log_k n)	Each iteration divides n by k, so the number of steps is logarithmic in base k.
Space	O(1)	Only a single integer variable total is used, no extra data structures.

The complexity is efficient because repeated division reduces n quickly, and no extra memory is required aside from the accumulator.

Test Cases

# test cases
solution = Solution()

assert solution.sumBase(34, 6) == 9  # Example 1
assert solution.sumBase(10, 10) == 1  # Example 2
assert solution.sumBase(1, 2) == 1  # Smallest n
assert solution.sumBase(100, 2) == 3  # Largest n, binary
assert solution.sumBase(100, 10) == 1  # n in base 10, single sum
assert solution.sumBase(15, 16) == 15  # n < k, single digit
assert solution.sumBase(7, 7) == 1  # n = k, result is 1+0

Test	Why
34, 6	Validates general conversion
10, 10	Base equal to 10, no conversion
1, 2	Smallest n
100, 2	Large n, binary conversion
100, 10	Largest n, base 10 sum
15, 16	n < k edge case
7, 7	n = k edge case

Edge Cases

One edge case is when n is less than k. In this situation, n itself is a single-digit number in base k, so the sum of digits is just n. This is handled correctly by the loop because n % k returns n and the loop ends after one iteration.

Another edge case is when k equals 10. No actual conversion is needed; the algorithm still works because n % 10 yields each digit of n, and integer division by 10 shifts the digits correctly.

A third edge case occurs when n is exactly divisible by k multiple times, for instance n = k^m. The algorithm correctly sums all digits by extracting each remainder in sequence until n becomes zero, ensuring no digits are missed.