Leetcode – Sum of Digits in Base K Solution

Spread the love

The “Sum of Digits in Base K” problem on Leetcode is an interesting exercise that merges the worlds of number theory and programming. This problem allows developers to explore foundational computer science concepts, such as number base conversions and loops, all while applying Python’s powerful programming capabilities. This article offers a comprehensive look at the problem, the constraints involved, and multiple Python-based solutions to tackle it.

Problem Statement

Given an integer n (in base 10) and a base k, return the sum of the digits of n after converting it 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.

Constraints:

  • 1 ≤ n ≤ 100
  • 2 ≤ k ≤ 10

Example:

Input: n = 34, k = 6

Output: 9

Approach 1: Base Conversion and Loop-based Summation

The first approach consists of two major steps:

  1. Convert the base 10 number n to base k.
  2. Sum up the digits of the resulting number.

Here’s how we can implement this in Python:

def sumBase(n, k):
    num_in_base_k = ""
    while n > 0:
        n, remainder = divmod(n, k)
        num_in_base_k += str(remainder)
        
    return sum(int(digit) for digit in num_in_base_k)

Time Complexity

Both the base conversion and the summation have a time complexity of O(log⁡k n).

Space Complexity

The space complexity is O(log⁡k n) due to storing the digits in a string.

Approach 2: On-the-Fly Summation

Instead of converting the entire number first and then summing the digits, we can sum the digits as we convert n to base k.

def sumBase(n, k):
    digit_sum = 0
    while n > 0:
        n, remainder = divmod(n, k)
        digit_sum += remainder
        
    return digit_sum

Time Complexity

This approach also has a time complexity of O(log⁡k n).

Space Complexity

The space complexity is O(1) since we are not storing the digits.

Unit Testing

It’s important to test the implementation against different test cases to ensure its correctness.

def test_sumBase():
    assert sumBase(34, 6) == 9
    assert sumBase(10, 10) == 1
    assert sumBase(21, 3) == 7
    print("All test cases pass")

test_sumBase()

Conclusion

The “Sum of Digits in Base K” problem offers a platform to delve into important computer science concepts, such as number base conversions and loop optimization. While the problem may appear to be math-heavy at first glance, solving it is straightforward once we apply the right computational logic. As with many problems in coding, there are often multiple paths to a solution, each with its own set of trade-offs. Here, we saw that we could either convert the entire number first or sum the digits on-the-fly, with the latter providing a slight edge in space complexity.

Leave a Reply