algoadvance

Leetcode 1837. Sum of Digits in Base K

Problem Statement

1837. Sum of Digits in Base K

Given an integer n (in base 10) and an integer k, return the sum of the digits of n after converting n from base 10 to base k.

Example 1:

Input: n = 34, k = 6
Output: 9
Explanation: 34 (base 10) is 54 in base 6. 5 + 4 = 9.

Example 2:

Input: n = 10, k = 10
Output: 1
Explanation: 10 (base 10) is 10 in base 10. 1 + 0 = 1.

Constraints:

Clarifying Questions

  1. Q: What should we do in case of invalid inputs, such as n < 1 or k < 2?
    • A: The problem statement guarantees that 1 <= n <= 100 and 2 <= k <= 10, so we don’t need to handle invalid inputs.
  2. Q: Are there any specific constraints on the output?
    • A: The output should always be a non-negative integer, which is the sum of the digits of the given number in the new base k.
  3. Q: Can we assume that the inputs n and k will always be integers?
    • A: Yes, the inputs are guaranteed to be integers within the given constraints.

Strategy

To solve the problem, follow these steps:

  1. Convert n from Base 10 to Base k:
    • Repeatedly divide the number n by k.
    • Store the remainders of these divisions which will be the digits in base k.
    • Build the number in the new base by placing remainders in reverse order.
  2. Sum the Digits:
    • As you obtain each remainder during conversion, you can directly add it to the sum, avoiding the need to construct the full number in base k.

Code

public class SumOfDigitsInBaseK {
    public int sumBase(int n, int k) {
        int sum = 0;
        
        while (n > 0) {
            sum += n % k;
            n /= k;
        }
        
        return sum;
    }

    public static void main(String[] args) {
        SumOfDigitsInBaseK solver = new SumOfDigitsInBaseK();
        
        // Test cases
        System.out.println(solver.sumBase(34, 6));  // Expected output: 9
        System.out.println(solver.sumBase(10, 10)); // Expected output: 1
    }
}

Time Complexity

  1. Conversion and Summation Process:
    • Each division operation decreases the value of n by a factor of k. The number of operations required is proportional to (log_k n).
    • Each division and modulus operation is O(1).

In summary, the time complexity of this solution is O(log k n), which is efficient given the constraints (1 \le n \le 100) and (2 \le k \le 10).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI