Sum of Digits in Base K solution and explanation
Google
9 more videos on this problem
Sum of Digits in Base K | Weekly Contest 238 | Leetcode | Easy Problems 1837TECH_ED · 3:28 · 752 views
1837. Sum of Digits in Base K (Leetcode Easy)Programming Live with Larry · 2:45 · 685 views
Sum of Digits in Base K | Leetcode 1837 | Converting Numbers From One Base To Another BaseAverageLeeter · 24:08 · 622 views
Sum of Digits in Base K | LeetCodeNalin Goyal · 6:34 · 401 views
Leetcode-1837 | Leetcode weekly contest - 238 | Sum of Digits in Base KGuddu Kumar · 3:48 · 305 views
LeetCode 1837 | Sum of Digits in Base K | %k, /k | JavaSleepy Cracker · 1:06 · 185 views
LeetCode Çözümleri - 1837. Sum of Digits in Base KSoner Gönül · 6:18 · 127 views
Leetcode solving 1837 Sum of Digits in Base KMath Geeks · 2:44 · 67 views
LeetCode 1837 – Sum of Digits in Base KPrashant Parmar · 4:31 · 18 views
Sum of Digits in Base K | LeetCode 1837 | Easy C++ Solution 🚀Harshil Patel · 0:57 · 17 views
The problem
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
Approach overview
Problem Overview: Given an integer n and a base k, convert n from base 10 into base k and return the sum of its digits in that base. The challenge is performing the base conversion efficiently without building unnecessary data structures.
Approach 1: Modulo and Division Method (O(logk n) time, O(1) space)
This approach directly simulates base conversion using arithmetic. Repeatedly take n % k to extract the least significant digit in base k, add it to a running sum, then update n = n / k. Each iteration removes one base‑k digit from the number. The process stops when n becomes zero. Since every step reduces the number by a factor of k, the loop runs about logk(n) times.
This is the most practical solution because it avoids storing the converted digits. Instead of building the entire representation first, you accumulate the sum as digits are generated. The algorithm uses only constant extra memory and performs simple arithmetic operations, making it extremely efficient for large inputs. This technique relies on basic math principles behind positional number systems.
Approach 2: Recursive Conversion (O(logk n) time, O(logk n) space)
The recursive approach mirrors how base conversion is often described mathematically. The idea is simple: the digit sum of n in base k equals (n % k) + sum(n / k). Each recursive call processes one digit and reduces the number by dividing it by k. The recursion stops when n becomes zero.
This version is conceptually elegant and clearly expresses the relationship between the number and its base‑k digits. However, it uses the call stack to maintain intermediate states, resulting in O(logk n) auxiliary space. For languages with limited recursion depth or performance-sensitive environments, the iterative method is typically preferred. Still, recursion is useful for demonstrating the structure of base conversion and practicing recursion patterns built on simple mathematical decomposition.
Recommended for interviews: The modulo and division method is the expected solution. It shows that you understand how base conversion works internally and can implement it with constant space. Mentioning the recursive form demonstrates deeper conceptual understanding, but the iterative version is cleaner and avoids unnecessary stack usage.
Approach 1: Modulo and Division Method
This 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.
def sum_of_digits_in_base_k(n, k):
sum_ = 0
while n > 0:
sum_ += n % k
n //= k
return sum_
n = 34
k = 6
print(sum_of_digits_in_base_k(n, k))public class SumDigits {
public static int sumOfDigitsInBaseK(int n, int k) {
int sum = 0;
while (n > 0) {
sum += n % k;
n /= k;
}
return sum;
}
public static void main(String[] args) {
int n = 34, k = 6;
System.out.println(sumOfDigitsInBaseK(n, k));
}
}#include <iostream>
int sumOfDigitsInBaseK(int n, int k) {
int sum = 0;
while (n > 0) {
sum += n % k;
n /= k;
}
return sum;
}
int main() {
int n = 34, k = 6;
std::cout << sumOfDigitsInBaseK(n, k) << std::endl;
return 0;
}function sumOfDigitsInBaseK(n, k) {
let sum = 0;
while (n > 0) {
sum += n % k;
n = Math.floor(n / k);
}
return sum;
}
let n = 34;
let k = 6;
console.log(sumOfDigitsInBaseK(n, k));#include <stdio.h>
int sumOfDigitsInBaseK(int n, int k) {
int sum = 0;
while (n > 0) {
sum += n % k;
n /= k;
}
return sum;
}
int main() {
int n = 34, k = 6;
printf("%d\n", sumOfDigitsInBaseK(n, k));
return 0;
}using System;
class Program {
static int SumOfDigitsInBaseK(int n, int k) {
int sum = 0;
while (n > 0) {
sum += n % k;
n /= k;
}
return sum;
}
static void Main() {
int n = 34, k = 6;
Console.WriteLine(SumOfDigitsInBaseK(n, k));
}
}The function sum_of_digits_in_base_k calculates the sum of the digits after converting n to base k using a loop and collecting the remainder.
Time Complexity: O(logk(n))
Space Complexity: O(1)
Approach 2: Recursive Conversion
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.
def sum_of_digits_in_base_k_recursive(n, k):
if n == 0:
return 0
return (n % k) + sum_of_digits_in_base_k_recursive(n // k, k)
n = 34
k = 6
print(sum_of_digits_in_base_k_recursive(n, k))public class SumDigitsRecursive {
public static int sumOfDigitsInBaseKRecursive(int n, int k) {
if (n == 0) return 0;
return (n % k) + sumOfDigitsInBaseKRecursive(n / k, k);
}
public static void main(String[] args) {
int n = 34, k = 6;
System.out.println(sumOfDigitsInBaseKRecursive(n, k));
}
}#include <iostream>
int sumOfDigitsInBaseKRecursive(int n, int k) {
if (n == 0) return 0;
return (n % k) + sumOfDigitsInBaseKRecursive(n / k, k);
}
int main() {
int n = 34, k = 6;
std::cout << sumOfDigitsInBaseKRecursive(n, k) << std::endl;
return 0;
}function sumOfDigitsInBaseKRecursive(n, k) {
if (n === 0) return 0;
return (n % k) + sumOfDigitsInBaseKRecursive(Math.floor(n / k), k);
}
let n = 34;
let k = 6;
console.log(sumOfDigitsInBaseKRecursive(n, k));#include <stdio.h>
int sumOfDigitsInBaseKRecursive(int n, int k) {
if (n == 0) return 0;
return (n % k) + sumOfDigitsInBaseKRecursive(n / k, k);
}
int main() {
int n = 34, k = 6;
printf("%d\n", sumOfDigitsInBaseKRecursive(n, k));
return 0;
}using System;
class Program {
static int SumOfDigitsInBaseKRecursive(int n, int k) {
if (n == 0) return 0;
return (n % k) + SumOfDigitsInBaseKRecursive(n / k, k);
}
static void Main() {
int n = 34, k = 6;
Console.WriteLine(SumOfDigitsInBaseKRecursive(n, k));
}
}This function recursively sums the digits of n in base k. If n becomes zero, it returns 0, else it adds the remainder to the ongoing sum.
Time Complexity: O(logk(n))
Space Complexity: O(logk(n))
Approach 3: Mathematics
We divide n by k and take the remainder until it is 0. The sum of the remainders gives the result.
The time complexity is O(log_{k}n), and the space complexity is O(1).
function sumBase(n: number, k: number): number {
let ans = 0;
while (n) {
ans += n % k;
n = Math.floor(n / k);
}
return ans;
}func sumBase(n int, k int) (ans int) {
for n > 0 {
ans += n % k
n /= k
}
return
}impl Solution {
pub fn sum_base(mut n: i32, k: i32) -> i32 {
let mut ans = 0;
while n != 0 {
ans += n % k;
n /= k;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Modulo and Division Method | Time Complexity: O(logk(n)) |
| Recursive Conversion | Time Complexity: O(logk(n)) |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Modulo and Division Method | O(log_k n) | O(1) | Best general solution. Efficient base conversion without storing digits. |
| Recursive Conversion | O(log_k n) | O(log_k n) | Useful for explaining the mathematical structure of base conversion or practicing recursion. |
Frequently asked questions
Is Sum of Digits in Base K easy or hard?
LeetCode classifies this problem as Easy. It mainly checks whether you understand how numbers are represented in different bases and how to extract digits using modulo and division.
Sum of Digits in Base K Python/Java solution
In Python or Java, implement a loop that repeatedly computes digit = n % k, adds it to a sum variable, and updates n = n // k (or n /= k in Java). Continue until n becomes zero. This approach runs in O(log_k n) time with constant memory.
How to solve Sum of Digits in Base K in O(n)?
The optimal solution does not require O(n) time. Instead, it runs in O(log_k n) time using repeated modulo and division operations. Each step extracts a single base‑k digit and adds it to the running sum.
What is the best approach for Sum of Digits in Base K?
The modulo and division method is the most efficient and commonly expected approach. Repeatedly compute n % k to get each base‑k digit and divide n by k to move to the next digit. This processes all digits in O(log_k n) time while using O(1) extra space.
Is Sum of Digits in Base K asked at Google/Amazon/Meta?
Problems involving base conversion and digit manipulation appear in interviews at companies like Amazon and Google, usually as warm‑up or easy questions. They test understanding of number systems, modulo arithmetic, and basic algorithmic thinking.
What data structure is used in Sum of Digits in Base K?
No special data structure is required. The optimal solution uses simple arithmetic operations with integers, specifically modulo and division, making it a straightforward math-based algorithm.
What is the time complexity of Sum of Digits in Base K?
The time complexity is O(log_k n) because each iteration extracts one digit in base k by dividing the number by k. The number of digits in base k is proportional to log base k of n.