#1680

Medium

LeetCode Problem Workspace

Concatenation of Consecutive Binary Numbers

Calculate the decimal value of concatenated binary numbers from 1 to n using efficient bit manipulation techniques.

Problem Statement

Given a positive integer n, generate a string by concatenating the binary representations of all integers from 1 to n in order. Return the decimal value of this concatenated binary string modulo 10^9 + 7.

For example, if n = 3, the binary representations are "1", "10", "11". Concatenating them results in "11011", whose decimal value is 27. Implement an algorithm that efficiently handles large n values up to 10^5 using math and bit manipulation patterns.

Examples

Example 1

Input: n = 1

Output: 1

"1" in binary corresponds to the decimal value 1.

Example 2

Input: n = 3

Output: 27

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

The concatenation results in "1101110010111011110001001101010111100". The decimal value of that is 118505380540. After modulo 109 + 7, the result is 505379714.

Constraints

1 <= n <= 105

Solution Approach

Iterative Bit Shift with Modulo

Initialize a result variable to 0. For each number from 1 to n, determine its binary length, shift the result left by that length, add the number, and apply modulo 10^9+7. This ensures that the concatenation is represented numerically without building large strings.

Optimized Shift Calculation

Precompute the bit length increases at powers of two to avoid recalculating log values repeatedly. This reduces the computational overhead and aligns with the math plus bit manipulation pattern by handling shifts efficiently.

Avoiding Overflow with Modular Arithmetic

Apply modulo after every addition and shift to prevent integer overflow. This keeps the calculation within the bounds of standard integer types and ensures correctness even when n approaches 10^5.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each number requires a constant-time shift and addition with modulo. Space complexity is O(1) as no extra arrays or strings are stored, only the running result and temporary variables.

What Interviewers Usually Probe

Candidate immediately recognizes the problem as math plus bit manipulation with shifting and modulo.
Candidate attempts naive string concatenation and is prompted to optimize using numeric shifts.
Candidate considers overflow and applies modulo iteratively to maintain correctness.

Common Pitfalls or Variants

Common pitfalls

Trying to concatenate actual binary strings leads to memory inefficiency and TLE for large n.
Forgetting to shift the result by the correct bit length of the current number causes incorrect decimal values.
Neglecting modulo at each step results in integer overflow and wrong answers for large n.

Follow-up variants

Return the concatenation in hexadecimal instead of decimal, still using bit manipulation to compute efficiently.
Calculate the sum of the decimal values of all prefixes of the concatenated binary string.
Compute the concatenation modulo a different prime, emphasizing modular arithmetic properties.

FAQ

What is the main trick to solving Concatenation of Consecutive Binary Numbers efficiently?

The key is to treat the concatenation numerically by shifting the accumulated result left by the current number's bit length and adding the number, applying modulo at each step.

Why is using actual binary string concatenation inefficient?

Concatenating strings for large n consumes excessive memory and causes time limit exceeded errors; numeric shifting is faster and avoids building large strings.

How do you calculate the bit length needed for each shift?

Use log2 of the number or track when the number reaches a power of two, increasing the shift length accordingly.

Can this approach handle n = 100,000 without overflow?

Yes, applying modulo 10^9+7 at each step ensures the numeric result stays within integer bounds, even for very large n.

Does this problem pattern always involve both math and bit manipulation?

Yes, the core pattern requires combining math for shifts and modulo with bit manipulation for binary representation handling.

terminal

Solution

Solution 1: Bit Manipulation

By observing the pattern of number concatenation, we can find that when concatenating to the $i$-th number, the result $ans$ formed by concatenating the previous $i-1$ numbers is actually shifted to the left by a certain number of bits, and then $i$ is added. The number of bits shifted is the number of binary digits in $i$.

1

2

3

4

5

6

7

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        ans = 0
        for i in range(1, n + 1):
            ans = (ans << i.bit_length() | i) % mod
        return ans

Solution 2: Bit Manipulation (Optimization)

In Solution 1, we need to calculate the number of binary digits of $i$ each time, which adds some extra computation. We can use a variable $\textit{shift}$ to record the current number of bits to shift. When $i$ is a power of $2$, $\textit{shift}$ needs to be incremented by $1$.

1

2

3

4

5

6

7

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        ans = 0
        for i in range(1, n + 1):
            ans = (ans << i.bit_length() | i) % mod
        return ans

Continue Practicing

#1688 count of matches in tournament #1799 maximize score after n operations #1806 minimum number of operations to reinitialize a permutation