1837. K 进制表示下的各位数字总和

🟢   🔖  数学  🔗 力扣 LeetCode

题目

Given an integer n (in base 10) and a base k, return _the sum of the digits of _n _after converting _n from base10 to basek.

After converting, each digit should be interpreted as a base 10 number, and the sum should be returned in base 10.

Example 1:

Input: n = 34, k = 6

Output: 9

Explanation: 34 (base 10) expressed in base 6 is 54. 5 + 4 = 9.

Example 2:

Input: n = 10, k = 10

Output: 1

Explanation: n is already in base 10. 1 + 0 = 1.

Constraints:

• 1 <= n <= 100
• 2 <= k <= 10

题目大意

给你一个整数 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 <= 100
• 2 <= k <= 10

解题思路

1. 转换为基数 k 的表示：将数字 n 转换为基数为 k 的表示可以通过反复除以 k 获得每一位。例如，使用取余操作 n % k 获取最低位，然后将 n 除以 k 来得到新的 n，重复此过程直到 n 为 0。

2. 累加数位和：每一次获取到一个数位的值之后，将其加到 sum 上。这样最终得到的 sum 就是转换后各个数位的和。

3. 结束条件：当 n 除到 0 时，所有数位的和就已经计算完成。

复杂度分析

• 时间复杂度：O(log_k n)，因为每次除以 k，数字的大小逐步减小，循环次数大约是 log_k n。
• 空间复杂度：O(1)，除了存储结果的 sum，没有其他额外的空间使用。

代码

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var sumBase = function (n, k) {
	let sum = 0;
	while (n > 0) {
		sum += n % k; // 获取当前最低位数
		n = Math.floor(n / k); // 去除最低位，继续处理下一位
	}
	return sum; // 返回所有数位的和
};

相关题目

题号	标题	题解	标签	难度	力扣
2843	统计对称整数的数目		数学 枚举	🟢	🀄️ 🔗