#1837

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Sum of Digits in Base K

Calculate the sum of digits of a number after converting it from base 10 to any given base using a math-driven approach.

math

Problem Statement

Given an integer n in base 10 and a target base k, convert n into base k and compute the sum of its digits. Each digit is interpreted in base 10 and added together to produce the final sum.

For example, if n = 34 and k = 6, 34 in base 6 is 54. Summing its digits, 5 + 4, results in 9. The solution should handle any n and k within the constraints and return the sum efficiently.

Examples

Example 1

Input: n = 34, k = 6

Output: 9

34 (base 10) expressed in base 6 is 54. 5 + 4 = 9.

Example 2

Input: n = 10, k = 10

Output: 1

n is already in base 10. 1 + 0 = 1.

Constraints

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

Solution Approach

Iterative Division and Remainder

Repeatedly divide n by k and collect remainders. Each remainder represents a digit in base k. Sum all remainders to get the final result.

Direct Mathematical Formula

While conversion is simplest iteratively, recognize that the sum of digits can be built mathematically using modulus and integer division in a loop, avoiding strings or arrays.

Edge Case Handling

Ensure n less than k returns n itself. Check small n like 1 or n equal to k multiples. These can produce off-by-one errors if handled incorrectly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log_k(n)) because each division reduces n by a factor of k. Space complexity is O(1) if only using integer variables, or O(log_k(n)) if storing digits in an array for summation.

What Interviewers Usually Probe

Candidate should immediately identify the need for base conversion.
Look for correct use of modulus and integer division for digit extraction.
Ensure the candidate handles edge cases where n < k or n is a multiple of k.

Common Pitfalls or Variants

Common pitfalls

Attempting to convert n to a string in base k incorrectly, which can produce wrong sums.
Forgetting to sum digits as base 10 numbers instead of characters or strings.
Overcomplicating the solution by using arrays or recursion when a simple loop suffices.

Follow-up variants

Sum of digits in base k for very large n, requiring optimized iteration.
Compute the sum of squares of digits in base k instead of the sum.
Apply the same digit-sum logic for negative numbers using absolute values.

FAQ

How do I convert a number to base k for this problem?

Use repeated integer division and modulus operations. Each remainder is a digit in base k.

Why is the sum of digits interpreted in base 10?

Even after conversion to base k, each digit is considered a standard number for addition.

Can I use strings or arrays to solve this problem?

Yes, but it is more efficient and cleaner to sum digits using modulus and division without extra storage.

What edge cases should I watch for in Sum of Digits in Base K?

Cases where n < k or n is a multiple of k can lead to errors if not handled correctly.

Is there a faster way than iterative division?

For this problem's constraints, iterative division is already efficient, and alternative formulas do not improve complexity significantly.

terminal

Solution

Solution 1: Mathematics

We divide $n$ by $k$ and take the remainder until it is $0$. The sum of the remainders gives the result.

1

2

3

4

5

6

7

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

Continue Practicing

#1835 find xor sum of all pairs bitwise and #1840 maximum building height #1830 minimum number of operations to make string sorted