Problem: Sum of Digits in Base K

Given an integer n (in base 10) and a base k, the task is to find the sum of the digits of n after converting it from base 10 to base k. The sum should be returned in base 10.

Solution Approach

The core idea is to repeatedly divide the input number n by the base k and sum the remainders. Each remainder represents a digit in the base k representation of n.

1. Initialization: Start with a sum ans initialized to 0.

2. Iteration: While n is greater than 0:

   • Calculate the remainder when n is divided by k (n % k). This remainder is a digit in the base k representation.
   • Add this remainder to ans.
   • Update n by integer division with k (n // k). This effectively removes the last digit in base k.

3. Return: After the loop finishes, ans will hold the sum of the digits in base k. Return ans.

Code Implementation (Multiple Languages)

The solution is straightforward and can be implemented efficiently in various programming languages. The following examples demonstrate the code in several popular languages:

Python:

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

Java:

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

C++:

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

JavaScript:

var sumBase = function(n, k) {
    let ans = 0;
    while (n > 0) {
        ans += n % k;
        n = Math.floor(n / k);
    }
    return ans;
};

Go:

func sumBase(n int, k int) int {
    ans := 0
    for n > 0 {
        ans += n % k
        n /= k
    }
    return ans
}

TypeScript:

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

Time and Space Complexity Analysis

• Time Complexity: The time complexity is O(logkn). This is because the number of iterations in the while loop is proportional to the number of digits in the base k representation of n, which is approximately logkn.

• Space Complexity: The space complexity is O(1) because we only use a constant amount of extra space to store the variables ans and potentially intermediate calculation results. The space used does not depend on the input size n.