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.
This is a more fundamental and efficient approach that calculates the sum of digits without explicitly constructing the base k representation as a string. It uses a loop and arithmetic operations (modulo and division) to extract and sum the digits one by one.
Algorithm
- Initialize a variable
sumto0. - Start a
whileloop that continues as long asnis greater than 0. - Inside the loop, calculate the remainder of
ndivided byk(n % k). This gives the value of the current least significant digit. - Add this remainder to
sum. - Update
nby performing integer division ofnbyk(n /= k). This effectively removes the least significant digit. - Once the loop terminates (when
nbecomes 0), return the finalsum.
Walkthrough
This method avoids creating an intermediate string by using a mathematical loop. The logic for converting a number to another base involves repeatedly taking the number modulo the new base to get the last digit, and then dividing the number by the new base to process the next digit. We can sum these digits as we extract them.
Let's trace this with n = 34 and k = 6:
- Initialize
sum = 0. - The
whileloop starts sincen(34) is greater than 0. - Iteration 1:
digit = n % k = 34 % 6 = 4.sum = sum + digit = 0 + 4 = 4.n = n / k = 34 / 6 = 5.
- Iteration 2:
nis now5, which is greater than 0.digit = n % k = 5 % 6 = 5.sum = sum + digit = 4 + 5 = 9.n = n / k = 5 / 6 = 0.
- Iteration 3:
nis now0. The loop conditionn > 0is false, so the loop terminates.
- The final value of
sum, which is9, is returned.
class Solution { public int sumBase(int n, int k) { int sum = 0; while (n > 0) { sum += n % k; n /= k; } return sum; }}Complexity
Time
O(log_k(n)) - The number of iterations in the `while` loop is determined by how many times we can divide `n` by `k` until it becomes 0. This is `log_k(n)`.
Space
O(1) - This approach only uses a few variables to store the input and the running sum. The space required does not depend on the size of the input `n`.
Trade-offs
Pros
Highly efficient, with optimal O(1) space complexity.
Does not require any intermediate data structures like strings or arrays.
The logic is fundamental to number theory and base conversion, making it a good demonstration of core programming concepts.
Cons
The logic might be slightly less intuitive for beginners compared to the string conversion method, as it combines the base conversion and summation steps.
Solutions
Solution
class Solution {public int sumBase(int n, int k) { int ans = 0; while (n != 0) { ans += n % k; n /= k; } return ans; }}/** * @param {number} n * @param {number} k * @return {number} */ var sumBase = function (n, k) { let ans = 0; while (n) { ans += n % k; n = Math.floor(n / k); } return ans; };class Solution {public: int sumBase(int n, int k) { int ans = 0; while (n) { ans += n % k; n /= k; } return ans; }};class Solution: def sumBase(self, n: int, k: int) -> int: ans = 0 while n: ans += n % k n //= k return ansVideo 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.