Code Implementation

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

class Solution {
public:
    int sumBase(int n, int k) {
        int total = 0;
        while (n > 0) {
            total += n % k;
            n /= k;
        }
        return total;
    }
};
      

class Solution {
    public int sumBase(int n, int k) {
        int total = 0;
        while (n > 0) {
            total += n % k;
            n /= k;
        }
        return total;
    }
}
      

var sumBase = function(n, k) {
    let total = 0;
    while (n > 0) {
        total += n % k;
        n = Math.floor(n / k);
    }
    return total;
};
      

Problem Description

Given two integers n and k, your task is to convert n from base 10 (decimal) to base k, and then return the sum of the digits of the resulting number in base k.

For example, if n = 34 and k = 6, you first represent 34 in base 6, which is 54 (since 5×6 + 4 = 34), and then compute 5 + 4 = 9.

• Constraints: 1 <= n <= 100, 2 <= k <= 10
• Each input will have one valid answer.

Thought Process

The problem asks us to convert a decimal number to another base and sum its digits. The first idea is to actually convert n into a string in base k, then sum its characters. But do we need to store the string? Not necessarily.

Instead, we can use a mathematical approach: repeatedly divide n by k, each time extracting the remainder, which gives us the next least significant digit in base k. We add up these remainders as we go.

This is much like how you would convert a number to another base by hand: divide by the base, write down the remainder, repeat with the quotient. Summing the remainders as we go gives us the answer directly, so we don't need to store the converted number.

Solution Approach

• Initialize a variable (let's call it total) to 0. This will hold the sum of the digits.
• Loop while n is greater than 0:
  • Find the current digit in base k by computing n % k. Add this digit to total.
  • Update n to n // k (integer division), which effectively removes the digit we just processed.
• When the loop ends, total contains the sum of the digits in base k.

This approach is efficient because:

• We never store the base-k representation as a string or array.
• We process each digit only once, in a single pass.
• The loop runs at most log_k(n) times, which is very small for the given constraints.

Example Walkthrough

Let's use n = 34 and k = 6 as an example.

• First iteration:
  • 34 % 6 = 4 (least significant digit in base 6)
  • Add 4 to total (total = 4)
  • 34 // 6 = 5
• Second iteration:
  • 5 % 6 = 5 (next digit)
  • Add 5 to total (total = 9)
  • 5 // 6 = 0
• Loop ends (since n is now 0).
• Final answer: 9

This matches our expectation: 34 in base 6 is "54", and 5 + 4 = 9.

Time and Space Complexity

• Brute-force approach: If we first convert n to a base k string and then sum the digits, the time complexity is O(log_k(n)), since that's the number of digits. Space complexity is also O(log_k(n)), as we store the string.
• Optimized approach (current solution): Time complexity is O(log_k(n)), since we process each digit once. Space complexity is O(1), since we only use a few integer variables and never store the whole number.

Summary

The problem can be solved efficiently by repeatedly dividing n by k and summing the remainders, which correspond to the digits of n in base k. This method is both fast and memory-efficient, as it avoids building the entire base-k representation. The key insight is realizing that the sum of digits can be found on-the-fly during the conversion process.