题目描述

给你一个整数 n（10 进制）和一个基数 k，请你将 n 从 10 进制表示转换为 k 进制表示，计算并返回转换后各位数字的 总和。

转换后，各位数字应当视作是 10 进制数字，且它们的总和也应当按 10 进制表示返回。

样例

输入：n = 34, k = 6
输出：9
解释：34 (10 进制) 在 6 进制下表示为 54。5 + 4 = 9。

输入：n = 10, k = 10
输出：1
解释：n 本身就是 10 进制。 1 + 0 = 1。

限制

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

算法

(模拟) $O(\log n)$

1. 将 10 进制转化为 k 进制时，每次用当前数字模 k 得到当前位的值，然后当前数字除以 k 下取整。不断这个流程直到 n 为 0。

时间复杂度

• 仅需要 $O(\log n)$ 次计算，故总时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int sumBase(int n, int k) {
        int ans = 0;

        for (; n; n /= k)
            ans += n % k;

        return ans;
    }
};