Skip to main content
Talentd

Sum of Digits in Base K - Solution & Explanation

EasyMath11 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 100
  • 2 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

The recursive function sumOfDigitsInBaseKRecursive computes the sum of digits of n in base k by recursively dividing n and accruing remainders.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Modulo and Division Method

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.

Recursive Conversion

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.

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Modulo and Division MethodO(log_k n)O(1)Best general solution. Efficient base conversion without storing digits.
Recursive ConversionO(log_k n)O(log_k n)Useful for explaining the mathematical structure of base conversion or practicing recursion.

Video Solution

Sum of Digits in Base K | Weekly Contest 238 | Leetcode | Easy Problems 1837 • TECH_ED • 752 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Sum of Digits in Base K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Symmetric Integers