Concatenation of Consecutive Binary Numbers

Problem Description

Given an integer n, the task is to form a binary string by concatenating the binary representations of all numbers from 1 to n in order. Then, return the decimal value of this binary string modulo 10^9 + 7.

Key Insights

• Instead of constructing one very long binary string (which could be huge for large n), update the result iteratively.
• Use bit shifts to “append” the current number in its binary representation to the result.
• For the current number i, determine its bit-length and update the result by shifting the previous result left by that bit-length and then adding i.
• Use modulo arithmetic at every step to prevent overflow and meet the problem constraints.

Space and Time Complexity

Time Complexity: O(n) – Each iteration computes the bit length and updates the result in constant time. Space Complexity: O(1) – Only a constant number of variables are used.

Solution

The solution uses an iterative approach:

1. Initialize a result variable to 0.
2. For each integer i from 1 to n:
   • Compute the number of bits required to represent i.
   • Left-shift the result by the bit-length of i and add i. Take modulo 10^9 + 7 to keep the value manageable.
3. Return the result.

Key data structures used are simple integer variables. The main trick is to use bit shifting to effectively “concatenate” binary numbers without explicitly constructing a huge string.

Code Solutions