题目

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:

  1. Input: n = 1
  2. Output: 1
  3. Explanation: "1" in binary corresponds to the decimal value 1.

Example 2:

  1. Input: n = 3
  2. Output: 27
  3. Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
  4. After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

  1. Input: n = 12
  2. Output: 505379714
  3. Explanation: The concatenation results in "1101110010111011110001001101010111100".
  4. The decimal value of that is 118505380540.
  5. After modulo 109 + 7, the result is 505379714.

Constraints:

  • 1 <= n <= 10^5

题意

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

思路

直接拼成字符串再计算勉强通过，也可以找到规律：1680. Concatenation of Consecutive Binary Numbers (M) - 图1%3DF(N-1)%3C%3Clen((N)_2)%2BN#card=math&code=F%28N%29%3DF%28N-1%29%3C%3Clen%28%28N%29_2%29%2BN)。

代码实现

Java

  1. class Solution {
  2.     public int concatenatedBinary(int n) {
  3.         long ans = 0;
  4.         for (int i = 1; i <= n; i++) {
  5.             int len = Integer.toBinaryString(i).length();
  6.             ans = ((ans << len) + i) % 1000000007;
  7.         }
  8.         return (int)ans;
  9.     }
  10. }