We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Digits in Base K

Number: 1965

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer n in base 10 and a base k, convert n from base 10 to base k and then compute the sum of the digits of the resulting number. The digits should be interpreted as base 10 numbers when summing.

Key Insights

  • Convert the number from base 10 to base k by repeatedly dividing by k and recording the remainder.
  • The remainders from each division represent the digits of the number in base k.
  • Sum the digits (as base 10 values) once the conversion is complete.
  • The constraint sizes are small, so a simple iterative approach is sufficient.

Space and Time Complexity

Time Complexity: O(log_k(n)) – The number of divisions needed is proportional to the number of digits in the new base. Space Complexity: O(1) – Only a few integer variables are used, and the sum can be computed on the fly.

Solution

We solve the problem by converting n from base 10 to base k using iterative division. In each iteration, we calculate the remainder (which becomes one digit in base k) and add it directly to a running sum. This avoids the need to store the full representation of the number. Once n is reduced to 0, the sum of all the digits (as computed by the remainders) is the answer. The approach leverages basic arithmetic operations and a loop, making it both efficient and easy to understand.

Code Solutions

# Function to compute the sum of digits in base k
def sum_base_k(n, k):
    # Initialize the sum of digits to 0
    total_sum = 0
    # Loop until n is reduced to 0
    while n > 0:
        # Find the remainder when n is divided by k (this is a digit in base k)
        digit = n % k
        # Add the digit (interpreted as a base 10 number) to the total sum
        total_sum += digit
        # Update n by dividing it by k to get the next digit
        n //= k
    # Return the computed sum of digits
    return total_sum

# Example usage:
print(sum_base_k(34, 6))  # Output: 9, because 34 in base 6 is '54', and 5 + 4 = 9
← Back to All Questions