标签: 数学
难度: Easy
给你一个整数 n（10 进制）和一个基数 k ，请你将 n 从 10 进制表示转换为 k 进制表示，计算并返回转换后各位数字的 总和 。
转换后，各位数字应当视作是 10 进制数字，且它们的总和也应当按 10 进制表示返回。
示例 1：
输入：n = 34, k = 6 输出：9 解释：34 (10 进制) 在 6 进制下表示为 54 。5 + 4 = 9 。
示例 2：
输入：n = 10, k = 10 输出：1 解释：n 本身就是 10 进制。 1 + 0 = 1 。
提示：
1 <= n <= 1002 <= k <= 10运行时间: 24 ms
内存: 16.0 MB
class Solution:
def sumBase(self, n: int, k: int) -> int:
# 将 n 从 10 进制转换为 k 进制，并计算各位数字的总和
sum_digits = 0
while n:
sum_digits += n % k
n //= k
return sum_digits
此题解的核心思路是利用数学除法和取余操作来将10进制数n转换为k进制数，并同时计算k进制数各个位的数字总和。具体做法是通过不断将n除以k并取其余数来得到k进制表示的每一位，余数直接加到总和中，然后更新n为n除以k的商，直到n为0。
时间复杂度: O(log_k(n))
空间复杂度: O(1)
class Solution:
def sumBase(self, n: int, k: int) -> int:
# 初始化总和为0
sum_digits = 0
# 当n不为0时循环
while n:
# 将n除以k的余数加到sum_digits上，余数即k进制的当前最低位
sum_digits += n % k
# 更新n为n除以k的商，向下整除
n //= k
# 返回k进制下各位数字的总和
return sum_digits
当n整除k时，余数确实为0，此时sum_digits被加上0，不改变其值。这种情况下，算法仍然有效，因为余数0正确地表示了k进制中该位的值。算法每次循环都处理n的最低位（k进制），并将n更新为除以k后的结果，因此，即使在余数为0的情况下，这个过程也能正确地继续直到n变为0。
题解中选择直接在循环中对n执行整除和取余的方法，是因为这种方式更为高效和直接。这种方法无需额外的空间来存储k进制的表示，也无需两个独立的步骤（转换和求和）。直接在遍历每一位的同时累加求和，减少了计算和存储开销。此外，这种方法也利用了整除和取余操作的性能优势，使得算法更为简洁和高效。
题解中的算法确实适用于k的整个有效范围（2到10）。当k较小或较大时，算法的效率可能略有不同。特别是当k接近n时，算法将很快完成转换，因为n将在一两次迭代后就被减至0。例如，如果n是9而k是8，只需要一次迭代就可以完成。在这种极端情况下，算法表现为高效，因为迭代次数减少。
题解中给出的算法可以在输入n为边界值时正确运行。对于n=1，该算法将直接在第一次迭代中添加1到sum_digits，并随后更新n为0，循环结束，输出为1。对于n=100，算法将根据k的值进行多次迭代，每次处理n的一个k进制位，最终将所有位的和作为结果。因此，无论n的值如何，算法都能正确计算出k进制表示下的各位数字总和。