本文主要是介绍1680. Concatenation of Consecutive Binary Numbers,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
Given an integer n
, return the decimal value of the binary string formed by concatenating the binary representations of 1
to n
in order, modulo 109 + 7
.
Example 1:
Input: n = 1 Output: 1 Explanation: "1" in binary corresponds to the decimal value 1.
Example 2:
Input: n = 3 Output: 27 Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11". After concatenating them, we have "11011", which corresponds to the decimal value 27.
Example 3:
Input: n = 12 Output: 505379714 Explanation: The concatenation results in "1101110010111011110001001101010111100". The decimal value of that is 118505380540. After modulo 109 + 7, the result is 505379714.
Constraints:
1 <= n <= 10^5
思路:
首先如果是真的按照思路走用字符串拼接的话肯定会超时,因为数据规模在10^5,只能或者更小。
根据观察得出规律:
n=1, f(1)=1
n=2, f(2)=[f(1) << 2] + 2 = 6
n=3, f(3)=[f(2) << 2] + 3 = 27
n=4, f(4)=[f(3) << 3] + 4 = 220
可以看出左移的位数和n的位数是相同的。
因此手动计算当前n的位数,然后进行左移和加n,中间不要忘记取模。另外因为数值过大,最初的记录答案的类型可以为long long。
代码:
class Solution {
public:
int concatenatedBinary(int n) {
int mode =1e9+7;
long long ans=1;
for(int i=2;i<=n;i++)
{
ans=ans<<count(i);
ans%=mode;
ans+=i;
ans%=mode;
}
return ans;
}
private:
int count(int n)
{
int ans=0;
while(n>0)
{
ans++;
n=n>>1;
}
return ans;
}
};
这篇关于1680. Concatenation of Consecutive Binary Numbers的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!