5 的不同幂次之和构成的序列求第 n 项
哪些公司问过
答案要点
- 序列是 5 的不同正整数次幂之和按升序排列,n 的二进制第 i 位对应 5^(i+1)
- 正确性:5^k 大于所有更低次幂之和 (5^k-5)/4,大小比较等价于二进制比较
- 实现:循环取 n 的最低位,幂 p 从 5 开始每轮乘 5,位为 1 时累加,O(log n)
- 验算:n=3 得 30,n=4 得 125,n=6 得 150
- 注意 n 从 1 计数与结果溢出,必要时用大整数或取模
易错点
- 用暴力枚举或优先队列生成,复杂度远高于 O(log n)
- 位与幂次错位,把第 0 位对应成 5^0
- 结果用 int 存储,n 稍大即溢出
面试官常见追问
- 如果序列包含 5^0,即 1、5、6、25…… 怎么改?
- 底数换成 3 或任意 b 还成立吗?
- 反过来给定一个数,如何判断它是否在序列中、是第几项?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。