跳至主要內容

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


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

🟢   🔖  数学  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

给你一个整数 n10 进制)和一个基数 k ,请你将 n10 进制表示转换为 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统计对称整数的数目数学 枚举🟢🀄️open in new window 🔗open in new window