Sum of Digits in Base K
EasyPrompt
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 <= 1002 <= k <= 10
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Convert the integer
nto its string representation in basekusing a built-in function (e.g.,Integer.toString(n, k)in Java). - Initialize a variable
sumto0. - 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.
Walkthrough
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:
- The Java function
Integer.toString(34, 6)is called, which returns the string"54". - A variable
sumis initialized to0. - The code then iterates through the characters of
"54".- For the character
'5',Character.getNumericValue('5')returns the integer5. The sum becomes0 + 5 = 5. - For the character
'4',Character.getNumericValue('4')returns the integer4. The sum becomes5 + 4 = 9.
- For the character
- After the loop, the final sum
9is returned.
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; }}Complexity
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)`.
Trade-offs
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.
Solutions
Solution
class Solution {public int sumBase(int n, int k) { int ans = 0; while (n != 0) { ans += n % k; n /= k; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.