Sum of Digits in Base K — Solution in Python, Java & C++
Sum of Digits in Base K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on math.
Sum of Digits in Base K is an easy coding problem on math, asked in Amazon and Infosys interviews.
- Difficulty: Easy
- Topics: Math
- Asked at: Amazon, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given integers n and k, convert n to base k and return the sum of its digits after conversion.
The returned sum is expressed in base 10.
Example 1
Input: n = 34, k = 6
Output: 9
Explanation: 34 in base 6 is 54, and 5 + 4 = 9.
Example 2
Input: n = 10, k = 10
Output: 1
Explanation: The base is 10, so the digits are 1 and 0.
Example 3
Input: n = 7, k = 2
Output: 3
Explanation: 7 in binary is 111.
Constraints
1 <= n <= 1002 <= k <= 10
Hints for Sum of Digits in Base K
Hint 1
You never need to build the base-
kstring.Hint 2
Each
n % kis one base-kdigit;n / kdrops it.Hint 3
Accumulate the remainders directly.
How to solve Sum of Digits in Base K
Repeated division extracts base-k digits from the least significant end, so summing the remainders gives the digit sum without ever forming the representation.
Approach
- While
n > 0, addn % kto a running total. - Set
n = n / kusing integer division. - Return the total.
Why it works
By definition n = Σ d_i · k^i with 0 <= d_i < k, and n % k yields d_0 while n / k shifts the remaining digits down — so the loop visits every digit exactly once.
Complexity
- Time —
O(log_k n) - Space —
O(1)
Pitfalls
- Converting to a string and summing characters works but is more code and needs digit-to-value care for bases above 10 (not an issue here, since
k <= 10). - Using floating-point division breaks the digit extraction.
Reference solution
Python
def sumBase(n: int, k: int) -> int:
total = 0
while n > 0:
total += n % k
n //= k
return totalJava
public static int sumBase(int n, int k) {
int total = 0;
while (n > 0) {
total += n % k;
n /= k;
}
return total;
}C++
int sumBase(int n, int k) {
int total = 0;
while (n > 0) {
total += n % k;
n /= k;
}
return total;
}JavaScript
var sumBase = function(n, k) {
let total = 0;
while (n > 0) {
total += n % k;
n = Math.floor(n / k);
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.