Sum of Digits in Base K

easy math base conversion

Problem

You are given a positive integer n written in base 10 and a base k (between 2 and 10). Convert n into its base-k representation, then add up those base-k digits as ordinary decimal numbers and return that sum.

Inputn = 34, k = 6

Output9

34 in base 6 is "54" (5·6 + 4 = 34). Adding the digits gives 5 + 4 = 9.

k (2-10)

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

function sumBase(n, k) {
  let total = 0;
  while (n > 0) {
    total += n % k;
    n = Math.floor(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;
    }
}

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

Explanation

The key insight is that you never actually need to build the base-k string. To sum the digits, you only need the digits themselves, and those fall out of the same divide-and-remainder trick used for any base conversion.

In any base k, the rightmost (least significant) digit of a number is exactly n % k. Once you have recorded that digit, you strip it off by doing n //= k, which is just integer division. What remains is the same number with its last base-k digit removed, so you can grab the next digit the same way.

So the whole algorithm is a single loop: while n is still positive, add n % k to a running total and shrink n with n //= k. When n hits 0 there are no digits left and total holds the answer.

Example: n = 34, k = 6. First pass: 34 % 6 = 4 (total 4), 34 // 6 = 5. Second pass: 5 % 6 = 5 (total 9), 5 // 6 = 0. Now n = 0, so we stop and return 9 — matching the digits of "54" in base 6.

Because each pass removes one base-k digit, the loop runs about log_k(n) times, which is very fast even for large n.

Time: O(log_k n) Space: O(1)