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.
- Initialize
ans
variable to store the sum of digits. - Iterate through the number
n
until it becomes 0:- Calculate the remainder
r = n % k
. Addr
to theans
variable. - Update
n = n // k
(integer division byk
).
- Calculate the remainder
- 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:
- Initialize
ans = 0
. - Iteration 1:
n = 34
,k = 6
,r = 34 % 6 = 4
. Addr
toans
:ans = 0 + 4 = 4
.- Update
n = 34 // 6 = 5
.
- Iteration 2:
n = 5
,k = 6
,r = 5 % 6 = 5
. Addr
toans
:ans = 4 + 5 = 9
.- Update
n = 5 // 6 = 0
.
- The loop stops since
n = 0
. Returnans = 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.