LeetCode 1837: Sum of Digits in Base K

Explanation

To solve this problem, we can convert the given number n from base 10 to base k. Then, we sum the digits of the converted number to get the final result. We can achieve this by repeatedly dividing the number by k to get the remainder which will be the least significant digit in base k. We keep track of the sum of digits as we go along.

Algorithm:

1. Initialize a variable sum to 0.
2. While n is greater than 0:
   • Calculate the remainder by taking n % k.
   • Add the remainder to sum.
   • Update n by doing integer division n / k.
3. Return the sum.

Time Complexity

The time complexity of this algorithm is O(logk(n)) where n is the input number and k is the base.

Space Complexity

The space complexity of this algorithm is O(1) as we are using a constant amount of extra space.

class Solution {
    public int sumBase(int n, int k) {
        int sum = 0;
        while (n > 0) {
            sum += n % k;
            n /= k;
        }
        return sum;
    }
}