Leetcode 1837: Sum of Digits in Base K

Input: The input consists of an integer n (in base 10) and a base k (2 <= k <= 10).

Example: n = 45, k = 7

Constraints:

• 1 <= n <= 100

• 2 <= k <= 10

Output: The output is a single integer representing the sum of the digits of n after converting it to base k, in base 10.

Example: 10

Constraints:

Goal: The goal is to calculate the sum of the digits of a number after converting it from base 10 to base k.

Steps:

• Convert the number n from base 10 to base k.

• Sum the digits of the resulting base k number.

• Return the sum of the digits in base 10.

Goal: The input values n and k are constrained within the specified range to ensure that the problem can be solved efficiently.

Steps:

• 1 <= n <= 100

• 2 <= k <= 10

Assumptions:

• The base k will be a valid integer between 2 and 10.

• Input: n = 45, k = 7

• Explanation: We first convert 45 from base 10 to base 7, resulting in '63'. The sum of the digits is 6 + 3 = 10, which is the final answer.

Approach: We will convert the number n from base 10 to base k and then sum the digits of the resulting base k number.

Observations:

• The conversion from base 10 to base k is straightforward using division and modulus operations.

• We can convert n to base k by repeatedly dividing n by k and storing the remainders. These remainders represent the digits in base k.

Steps:

• Initialize a variable to hold the sum of the digits.

• Perform division and modulus operations to convert n to base k, collecting the digits.

• Add the digits to the sum variable and return the result.

Empty Inputs:

• n should always be at least 1, so there are no empty inputs.

Large Inputs:

• Ensure that the function handles values of n up to 100 efficiently.

Special Values:

• Consider values of n that are already in base 10 or are powers of k.

Constraints:

• Ensure that the number is correctly converted to base k and that the sum is calculated properly.

int sumBase(int n, int k) {
    int res=0;
    while(n!=0)
    {
        res+=(n%k);
        n/=k;
    }
    return res;
}

1 : Function Definition

int sumBase(int n, int k) {

Defines the function `sumBase` which takes two parameters, `n` (the number) and `k` (the base), and returns the sum of the digits of `n` in base `k`.

2 : Variable Initialization

    int res=0;

Initializes the variable `res` to store the running sum of the digits in base `k`.

3 : While Loop

    while(n!=0)

Starts a while loop that continues as long as `n` is not zero, processing each digit of `n` in base `k`.

4 : Digit Calculation

        res+=(n%k);

Calculates the current digit in base `k` by taking the remainder of `n` when divided by `k`, and adds it to `res`.

5 : Base Division

        n/=k;

Divides `n` by `k` to remove the current digit and move to the next one in the next iteration.

6 : Return Statement

    return res;

Returns the accumulated sum `res`, which is the sum of the digits of `n` in base `k`.

Best Case: O(log n)

Average Case: O(log n)

Worst Case: O(log n)

Description: The time complexity is logarithmic in n, as we repeatedly divide n by k until it becomes 0.

Best Case: O(1)

Worst Case: O(log n)

Description: The space complexity is O(log n) due to the storage required for the digits of the base k representation.

Leetcode 1837: Sum of Digits in Base K

Explore →