题目描述
给你一个整数 n
,请你将 1
到 n
的二进制表示连接起来,并返回连接结果对应的 十进制 数字对 10^9 + 7
取余的结果。
样例
示例1
输入:n = 1
输出:1
解释:二进制的 "1" 对应着十进制的 1 。
示例2
输入:n = 3
输出:27
解释:二进制下,1,2 和 3 分别对应 "1" ,"10" 和 "11" 。
将它们依次连接,我们得到 "11011" ,对应着十进制的 27 。
示例2
输入:n = 12
输出:505379714
解释:连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 10^9 + 7 取余后,结果为 505379714 。
提示
1 <= n <= 10^5
算法1
(位运算) $O(nlog(n))$
- 令
f(n)
表示连接1-n
的答案 f(n + 1)
则等于 $f(n)$ 连接 $(n + 1)$的二进制表示后模1e9+7
- 连接可以表示为 $(f(n) << len(n_2)) + (n + 1)_2$
- 因此枚举
1-n
,递推求解答案即可。
时间复杂度
- 枚举所有数字需要$O(n)$的时间
- 每次需要$O(log(n))$的时间计算出$len(x_2)$ (其实最多
32
次计算) - 故总时间复杂度为$O(nlog(n))$
C++ 代码
class Solution {
public:
int concatenatedBinary(int n) {
const int mod = 1e9 + 7;
long long ans = 0;
for(int i = 1; i <= n; i++){
int len = 0;
int t = i;
while(t) {
len++;
t >>= 1;
}
ans = (ans << len) + i;
ans %= mod;
}
return ans;
}
};
时间复杂度是 $O(n \log n)$ 的
别骂了别骂了