1837. K 进制表示下的各位数字总和
1837. K 进制表示下的各位数字总和
题目
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
解题思路
转换为基数
k
的表示:将数字n
转换为基数为k
的表示可以通过反复除以k
获得每一位。例如,使用取余操作n % k
获取最低位,然后将n
除以k
来得到新的n
,重复此过程直到n
为 0。累加数位和:每一次获取到一个数位的值之后,将其加到
sum
上。这样最终得到的sum
就是转换后各个数位的和。结束条件:当
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 | 统计对称整数的数目 | 数学 枚举 | 🟢 | 🀄️ 🔗 |