Sum of Digits in Base K

Difficulty: Easy | Acceptance: 78.70% | Paid: No Topics: Math

Given an integer n (in base 10) and a base k, return the sum of the digits of n after converting n from base 10 to base k.

Examples

Example 1:

Input: n = 34, k = 6
Output: 9
Explanation: 34 (base 10) expressed in base 6 is 54. 5 + 4 = 9.

Example 2:

Input: n = 10, k = 10
Output: 1
Explanation: n is already in base 10. 1 + 0 = 1.

Constraints

1 <= n <= 100
2 <= k <= 10

Table of Contents

• Examples
• Constraints
• Repeated Division
• Recursive Approach
• String Conversion

Repeated Division

Intuition The standard method for base conversion involves repeatedly dividing the number by the target base and collecting remainders, which represent the digits in the new base.

Steps

• Initialize sum to 0
• While n is greater than 0, get the remainder when divided by k
• Add the remainder to the sum
• Divide n by k (integer division)
• Return the sum

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

Complexity

• Time: O(logₖ(n)) - number of digits in base k
• Space: O(1) - only using a constant amount of extra space
• Notes: This is the most efficient approach with minimal space usage

Recursive Approach

Intuition We can use recursion to process each digit by taking the remainder and recursively processing the quotient.

Steps

• Base case: if n is 0, return 0
• Return the remainder (n % k) plus the recursive call on n // k

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

Complexity

• Time: O(logₖ(n)) - number of recursive calls equals number of digits
• Space: O(logₖ(n)) - recursion stack depth equals number of digits
• Notes: Elegant but uses more stack space than iterative approach

String Conversion

Intuition Convert the number to its string representation in base k, then iterate through characters to sum their numeric values.

Steps

• Build the base k representation string by repeatedly getting remainders
• Convert each character back to its numeric value
• Sum all values

class Solution:
    def sumBase(self, n: int, k: int) -> int:
        result = ""
        while n > 0:
            result = str(n % k) + result
            n //= k
        return sum(int(c) for c in result)

Complexity

• Time: O(logₖ(n)) - building string and summing digits
• Space: O(logₖ(n)) - storing the string representation
• Notes: Less efficient due to string operations but demonstrates the concept clearly