Concatenation of Consecutive Binary Numbers (M)

题目

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

题意

将整数1-n的二进制拼成一个长二进制，求这个长二进制代表的十进制数。

思路

直接拼成字符串再计算勉强通过，也可以找到规律：\(F(N)=F(N-1)<<len((N)_2)+N\)。

代码实现

Java

class Solution {
    public int concatenatedBinary(int n) {
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            int len = Integer.toBinaryString(i).length();
            ans = ((ans << len) + i) % 1000000007;
        }
        return (int)ans;
    }
}

1680. Concatenation of Consecutive Binary Numbers (M)

原文：https://www.cnblogs.com/mapoos/p/14336666.html