# Sum of Digits in Base K
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-of-digits-in-base-k)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-digits-in-base-k
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
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`.

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

**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`

# Approaches
## String Conversion and Summation
This approach leverages built-in language features to first convert the base-10 number `n` into its string representation in base `k`. Once we have this string, we can iterate through its characters, convert each character back to its integer value, and accumulate the sum.
**Time:** O(log_k(n)) - The conversion to a string takes `O(log_k(n))` time. Iterating through the resulting string of length `log_k(n)` also takes `O(log_k(n))` time. · **Space:** O(log_k(n)) - An intermediate string is created to store the base `k` representation of `n`. The length of this string is proportional to the number of digits, which is `log_k(n)`.
**Pros:** Simple and easy to read, especially for those familiar with the language's built-in functions.; The logic is very direct and follows the problem statement literally: "convert n... then sum the digits".
**Cons:** Less efficient in terms of space due to the allocation of an intermediate string.; Relies on a specific built-in function, which might not be available or might have different behavior in other programming languages.
### Explanation
This approach first converts the number `n` into its base `k` string representation and then sums up the digits from that string. This is a straightforward implementation that directly follows the problem description.

For example, with `n = 34` and `k = 6`:
1.  The Java function `Integer.toString(34, 6)` is called, which returns the string `"54"`.
2.  A variable `sum` is initialized to `0`.
3.  The code then iterates through the characters of `"54"`.
    *   For the character `'5'`, `Character.getNumericValue('5')` returns the integer `5`. The sum becomes `0 + 5 = 5`.
    *   For the character `'4'`, `Character.getNumericValue('4')` returns the integer `4`. The sum becomes `5 + 4 = 9`.
4.  After the loop, the final sum `9` is returned.

```java
class Solution {
    public int sumBase(int n, int k) {
        String baseKString = Integer.toString(n, k);
        int sum = 0;
        for (char c : baseKString.toCharArray()) {
            // Character.getNumericValue(c) converts a character digit to its int value.
            // For example, '5' becomes 5.
            sum += Character.getNumericValue(c);
        }
        return sum;
    }
}
```
### Algorithm
*   Convert the integer `n` to its string representation in base `k` using a built-in function (e.g., `Integer.toString(n, k)` in Java).
*   Initialize a variable `sum` to `0`.
*   Iterate over each character in the generated string.
*   For each character, convert it to its corresponding integer value (e.g., using `Character.getNumericValue(c)`).
*   Add this integer value to `sum`.
*   After the loop finishes, return `sum`.

## Iterative Division and Modulo
This is a more fundamental and efficient approach that calculates the sum of digits without explicitly constructing the base `k` representation as a string. It uses a loop and arithmetic operations (modulo and division) to extract and sum the digits one by one.
**Time:** O(log_k(n)) - The number of iterations in the `while` loop is determined by how many times we can divide `n` by `k` until it becomes 0. This is `log_k(n)`. · **Space:** O(1) - This approach only uses a few variables to store the input and the running sum. The space required does not depend on the size of the input `n`.
**Pros:** Highly efficient, with optimal O(1) space complexity.; Does not require any intermediate data structures like strings or arrays.; The logic is fundamental to number theory and base conversion, making it a good demonstration of core programming concepts.
**Cons:** The logic might be slightly less intuitive for beginners compared to the string conversion method, as it combines the base conversion and summation steps.
### Explanation
This method avoids creating an intermediate string by using a mathematical loop. The logic for converting a number to another base involves repeatedly taking the number modulo the new base to get the last digit, and then dividing the number by the new base to process the next digit. We can sum these digits as we extract them.

Let's trace this with `n = 34` and `k = 6`:
*   Initialize `sum = 0`.
*   The `while` loop starts since `n` (34) is greater than 0.
*   **Iteration 1:**
    *   `digit = n % k = 34 % 6 = 4`.
    *   `sum = sum + digit = 0 + 4 = 4`.
    *   `n = n / k = 34 / 6 = 5`.
*   **Iteration 2:**
    *   `n` is now `5`, which is greater than 0.
    *   `digit = n % k = 5 % 6 = 5`.
    *   `sum = sum + digit = 4 + 5 = 9`.
    *   `n = n / k = 5 / 6 = 0`.
*   **Iteration 3:**
    *   `n` is now `0`. The loop condition `n > 0` is false, so the loop terminates.
*   The final value of `sum`, which is `9`, is returned.

```java
class Solution {
    public int sumBase(int n, int k) {
        int sum = 0;
        while (n > 0) {
            sum += n % k;
            n /= k;
        }
        return sum;
    }
}
```
### Algorithm
*   Initialize a variable `sum` to `0`.
*   Start a `while` loop that continues as long as `n` is greater than 0.
*   Inside the loop, calculate the remainder of `n` divided by `k` (`n % k`). This gives the value of the current least significant digit.
*   Add this remainder to `sum`.
*   Update `n` by performing integer division of `n` by `k` (`n /= k`). This effectively removes the least significant digit.
*   Once the loop terminates (when `n` becomes 0), return the final `sum`.

# Solutions
### Java

```java
class Solution {
public
  int sumBase(int n, int k) {
    int ans = 0;
    while (n != 0) {
      ans += n % k;
      n /= k;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @param {number} k * @return {number} */ var sumBase =
  function (n, k) {
    let ans = 0;
    while (n) {
      ans += n % k;
      n = Math.floor(n / k);
    }
    return ans;
  };

```

### CPP

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

```

### Python

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

```