Problem

Given an integer n (in base 10) and a base k, return _thesum of the digits of _n _after converting _n from base10 to basek.

After converting, each digit should be interpreted as a base 10 number, and the sum should be returned in base 10.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Constraints

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

Solution

Method 1 – Repeated Division

Intuition

Convert the number to base k by repeatedly dividing by k and summing the remainders. Each remainder is a digit in the base k representation.

Approach

  1. Initialize a sum variable to 0.
  2. While n > 0, add n % k to the sum and set n = n // k.
  3. Return the sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int sumBase(int n, int k) {
        int ans = 0;
        while (n > 0) {
            ans += n % k;
            n /= k;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8

func sumBase(n int, k int) int {
    ans := 0
    for n > 0 {
        ans += n % k
        n /= k
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int sumBase(int n, int k) {
        int ans = 0;
        while (n > 0) {
            ans += n % k;
            n /= k;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun sumBase(n: Int, k: Int): Int {
        var num = n
        var ans = 0
        while (num > 0) {
            ans += num % k
            num /= k
        }
        return ans
    }
}
1
2
3
4
5
6
7

class Solution:
    def sumBase(self, n: int, k: int) -> int:
        ans = 0
        while n > 0:
            ans += n % k
            n //= k
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn sum_base(mut n: i32, k: i32) -> i32 {
        let mut ans = 0;
        let mut n = n;
        while n > 0 {
            ans += n % k;
            n /= k;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    sumBase(n: number, k: number): number {
        let ans = 0;
        while (n > 0) {
            ans += n % k;
            n = Math.floor(n / k);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log_k n) — Each division by k reduces n, so the number of steps is proportional to the number of digits in base k.
  • 🧺 Space complexity: O(1) — Only a few variables are used.