Leetcode 1837. Sum of Digits in Base K Solution

Problem Explanation

Given an integer n represented in base 10, we are asked to convert it to another base k and then return the sum of the digits of n after converting it to base k. Each digit should be interpreted as a base 10 number, and the sum should be returned in base 10.

Example

Let's consider the example with n = 34 and k = 6. Converting 34 from base 10 to base 6 results in the number 54. To find the desired sum, we should add the digits of the number obtained in base 6, which is 5 + 4 = 9.

Approach

The approach used for this problem is simple. We'll perform integer division and modulus operations with respect to the given base k while the number n is greater than 0.

1. Initialize ans variable to store the sum of digits.
2. Iterate through the number n until it becomes 0:
   • Calculate the remainder r = n % k. Add r to the ans variable.
   • Update n = n // k (integer division by k).
3. Return the ans variable.

Since the given numbers are small (1 <= n <= 100 and 2 <= k <= 10), this iterative approach runs efficiently.

Example

Let's walk through the example n = 34, k = 6 using the approach described above:

1. Initialize ans = 0.
2. Iteration 1:
   • n = 34, k = 6, r = 34 % 6 = 4. Add r to ans: ans = 0 + 4 = 4.
   • Update n = 34 // 6 = 5.
3. Iteration 2:
   • n = 5, k = 6, r = 5 % 6 = 5. Add r to ans: ans = 4 + 5 = 9.
   • Update n = 5 // 6 = 0.
4. The loop stops since n = 0. Return ans = 9.

Solution in Python

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

Solution in Java

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

Solution in JavaScript

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

Solution in C++

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

Solution in C#

1public class Solution {
2    public int SumBase(int n, int k) {
3        int ans = 0;
4
5        while (n > 0) {
6            ans += n % k;
7            n /= k;
8        }
9
10        return ans;
11    }
12}
13```## Conclusion
14
15In this article, we demonstrated an efficient iterative solution for converting a base 10 integer `n` to base `k` and then finding the sum of its digits. The solution runs in O(log(n)) time complexity.