Problem Description

Given an integer n, you need to concatenate the binary representations of all numbers from 1 to n in order, then convert the resulting binary string back to its decimal value. Return this decimal value modulo 10^9 + 7.

For example, if n = 3:

• Binary of 1 is "1"
• Binary of 2 is "10"
• Binary of 3 is "11"
• Concatenating them gives "11011"
• Converting "11011" to decimal gives 27
• Return 27 % (10^9 + 7) = 27

The solution uses bit manipulation to efficiently compute this value. Instead of actually creating the concatenated binary string, it builds the result by shifting the current answer left by the appropriate number of bits (equal to the bit length of the current number i) and then using bitwise OR to append i. This is mathematically equivalent to concatenating the binary representations but much more efficient.

The key insight is that concatenating binary number i to the existing result is the same as:

1. Shifting the existing result left by bit_length(i) positions
2. Adding (or OR-ing) the value i to fill those positions

The modulo operation is applied at each step to prevent integer overflow.

Intuition

When we concatenate binary strings, what we're really doing mathematically is shifting bits. Think about concatenating "10" and "11" - we get "1011". This is equivalent to taking the decimal value 2 (which is "10" in binary), shifting it left by 2 positions (since "11" has 2 bits), and then adding 3 (which is "11" in decimal).

The key observation is that concatenating binary strings is the same as:

• Taking the current accumulated value
• Shifting it left by the number of bits in the next number
• Adding the next number to fill those new bit positions

For example, if we have accumulated "110" (decimal 6) and want to append "11" (decimal 3):

• We shift 6 left by 2 bits: 6 << 2 = 24 (binary "11000")
• We add 3: 24 + 3 = 27 (binary "11011")

This gives us the concatenated result without actually working with strings!

The beauty of this approach is that we can use the bit_length() method to determine how many positions to shift. For any number i, i.bit_length() tells us exactly how many bits we need to shift the accumulated result before adding i.

Since we only care about the final decimal value modulo 10^9 + 7, we can apply the modulo operation at each step to keep the numbers manageable and prevent overflow. The bitwise OR operation (|) is used instead of addition since we're filling empty bit positions, though addition would work the same way here since the shifted bits and the new bits don't overlap.

Learn more about Math patterns.

Solution Approach

The implementation uses bit manipulation to efficiently build the concatenated binary value without creating actual binary strings.

Algorithm Steps:

1. Initialize ans = 0 to store our accumulated result and set mod = 10^9 + 7 for the modulo operation.

2. Iterate through each number i from 1 to n:

   • Calculate the number of bits in i using i.bit_length()
   • Shift the current ans left by that many bits: ans << i.bit_length()
   • Use bitwise OR to append i to the shifted result: (ans << i.bit_length()) | i
   • Apply modulo to keep the number manageable: % mod

Key Pattern - Bit Shifting Optimization:

As mentioned in the reference approach, there's a pattern to observe: when we reach a power of 2, the number of bits increases by 1. For example:

• Numbers 1 has 1 bit
• Numbers 2-3 have 2 bits
• Numbers 4-7 have 3 bits
• Numbers 8-15 have 4 bits

This means we could optimize further by tracking when the bit length changes instead of calculating it each time. However, the given solution calculates bit_length() for each i, which is still efficient since bit_length() is an O(1) operation.

Why This Works:

For each number i, the operation (ans << i.bit_length() | i) is mathematically equivalent to:

• Moving all existing bits in ans to the left by i.bit_length() positions
• Filling the newly created rightmost positions with the bits of i

This perfectly simulates the concatenation of binary strings but operates directly on integers, making it much more efficient than string manipulation.

The modulo operation is applied at each step to prevent integer overflow while preserving the correctness of the final result modulo 10^9 + 7.

Example Walkthrough

Let's walk through the solution with n = 4 to see how the bit manipulation approach works:

Initial State:

• ans = 0 (binary: empty)
• mod = 10^9 + 7

Iteration 1: i = 1

• Binary of 1 is "1" (1 bit)
• ans = (0 << 1) | 1 = 0 | 1 = 1
• Binary result so far: "1"
• ans = 1 % mod = 1

Iteration 2: i = 2

• Binary of 2 is "10" (2 bits)
• Current ans = 1 (binary: "1")
• Shift ans left by 2: 1 << 2 = 4 (binary: "100")
• OR with 2: 4 | 2 = 6 (binary: "110")
• Binary result so far: "110" (concatenation of "1" and "10")
• ans = 6 % mod = 6

Iteration 3: i = 3

• Binary of 3 is "11" (2 bits)
• Current ans = 6 (binary: "110")
• Shift ans left by 2: 6 << 2 = 24 (binary: "11000")
• OR with 3: 24 | 3 = 27 (binary: "11011")
• Binary result so far: "11011" (concatenation of "110" and "11")
• ans = 27 % mod = 27

Iteration 4: i = 4

• Binary of 4 is "100" (3 bits)
• Current ans = 27 (binary: "11011")
• Shift ans left by 3: 27 << 3 = 216 (binary: "11011000")
• OR with 4: 216 | 4 = 220 (binary: "11011100")
• Binary result so far: "11011100" (concatenation of all: "1" + "10" + "11" + "100")
• ans = 220 % mod = 220

Final Result: 220

The concatenated binary string is "11011100" which equals 220 in decimal. This demonstrates how shifting and OR-ing builds the same result as string concatenation but operates directly on integers.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the given integer. The algorithm iterates through numbers from 1 to n exactly once in the for loop. Within each iteration, the operations performed are:

• i.bit_length(): This operation takes O(log i) time, but since we're looking at the overall complexity and log i ≤ log n, and summing up O(log 1) + O(log 2) + ... + O(log n) = O(n log n) would be an overestimate. However, the bit_length operation in Python is typically implemented to run in O(1) time as it just reads the bit representation length.
• Left shift operation ans << i.bit_length(): O(1)
• Bitwise OR operation |: O(1)
• Modulo operation %: O(1)

Therefore, each iteration performs constant time operations, resulting in an overall time complexity of O(n).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space:

• Variable mod: stores a constant value
• Variable ans: stores the accumulated result (single integer)
• Variable i: loop counter

No additional data structures that grow with input size are used, so the space complexity remains constant regardless of the value of n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Apply Modulo at Each Step

Pitfall: A common mistake is applying the modulo operation only at the end instead of during each iteration:

# WRONG - This can cause integer overflow for large n
def concatenatedBinary(self, n: int) -> int:
    result = 0
    for i in range(1, n + 1):
        result = (result << i.bit_length()) | i
    return result % (10**9 + 7)  # Modulo only at the end

Why it's problematic: For large values of n, the intermediate result can grow exponentially and exceed integer limits, causing overflow or memory issues even in Python (which has arbitrary precision integers but still has practical memory limits).

Solution: Apply modulo at each iteration to keep the number bounded:

# CORRECT - Apply modulo at each step
def concatenatedBinary(self, n: int) -> int:
    MOD = 10**9 + 7
    result = 0
    for i in range(1, n + 1):
        result = ((result << i.bit_length()) | i) % MOD
    return result

2. Using String Concatenation Instead of Bit Manipulation

Pitfall: Attempting to solve this problem by actually concatenating binary strings:

# INEFFICIENT - String manipulation approach
def concatenatedBinary(self, n: int) -> int:
    binary_str = ""
    for i in range(1, n + 1):
        binary_str += bin(i)[2:]  # Remove '0b' prefix
    return int(binary_str, 2) % (10**9 + 7)

Why it's problematic:

• String concatenation has O(n²) time complexity due to string immutability
• Converting a very long binary string to integer is computationally expensive
• Memory usage grows linearly with the length of the concatenated string

Solution: Use the bit manipulation approach as shown in the original solution, which operates directly on integers and has O(n) time complexity with O(1) space.

3. Incorrect Bit Shifting Order

Pitfall: Confusing the order of operations or using addition instead of OR:

# WRONG - Using addition instead of OR
result = ((result << i.bit_length()) + i) % MOD

# WRONG - Shifting i instead of result
result = ((i << result.bit_length()) | result) % MOD

Why it's problematic:

• Addition can cause incorrect results when there's bit overlap
• Shifting the wrong value completely breaks the concatenation logic

Solution: Always shift the accumulated result left, then OR with the current number:

# CORRECT
result = ((result << i.bit_length()) | i) % MOD