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 <= 10This approach involves converting the number from base 10 to base k by repeatedly dividing the number by k and taking the remainder. The remainders give the digits of the number in base k, and these digits are then summed up.
The function sumOfDigitsInBaseK takes an integer n and a base k. It then converts n to base k by repeatedly dividing n by k, taking the remainder as the digit. These digits are added together to get the sum of digits in base k.
C++
Java
Python
C#
JavaScript
Time Complexity: O(logk(n)), because at each step we divide the number by k.
Space Complexity: O(1), as we use only a fixed amount of extra space.
This approach uses a recursive function to convert the number into base k and sum the digits. Each recursive call reduces the problem size by one digit.
The recursive function sumOfDigitsInBaseKRecursive computes the sum of digits of n in base k by recursively dividing n and accruing remainders.
C++
Java
Python
C#
JavaScript
Time Complexity: O(logk(n)), equivalent to the iterative method due to the number of recursive calls.
Space Complexity: O(logk(n)), due to the call stack.
| Approach | Complexity |
|---|---|
| Modulo and Division Method | Time Complexity: O(logk(n)), because at each step we divide the number by k. |
| Recursive Conversion | Time Complexity: O(logk(n)), equivalent to the iterative method due to the number of recursive calls. |
LeetCode 1281: Subtract the Product and Sum of Digits of Integer - Interview Prep Ep 25 • Fisher Coder • 3,397 views views
Watch 9 more video solutions →Practice Sum of Digits in Base K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor