Concatenation of Consecutive Binary Numbers - Video Solutions

Problem Overview: Given an integer n, build a binary string by concatenating the binary representations of numbers from 1 to n in order. Convert the resulting binary value to decimal and return it modulo 1e9 + 7. Directly forming the full binary string becomes expensive as n grows, so the goal is to append bits efficiently while keeping the number within modulo limits.

Approach 1: Binary String Accumulation (O(n log n) time, O(n log n) space)

This approach simulates the process literally. Iterate from 1 to n, convert each number to its binary form using built-in conversion, and append it to a growing string. After building the final binary string, convert it to a decimal value and apply modulo 1e9 + 7. The logic is easy to reason about and mirrors the problem statement exactly.

The drawback is memory and runtime overhead. The resulting binary string grows to roughly O(n log n) bits because each number contributes up to log2(n) bits. String concatenation and large integer parsing also slow things down. This approach works for small inputs but struggles with large n. It mainly helps you understand the mechanics of binary concatenation before optimizing.

Approach 2: Bit Manipulation (O(n) time, O(1) space)

The optimal solution avoids building a string entirely. Instead, treat the result as a number and append bits using left shifts. When you append the binary representation of a number i, shift the current result left by the number of bits in i, then add i. In code this looks like result = ((result << bits) | i) % MOD.

The key detail is tracking how many bits i contains. Every time i reaches a power of two (1, 2, 4, 8, ...), the bit length increases by one. Detect this with the condition (i & (i - 1)) == 0. This technique comes from bit manipulation and lets you update the bit count in constant time.

This solution processes each number once and performs only simple bit shifts and modulo operations. The runtime is O(n) and space is O(1). The logic also highlights the mathematical structure of the problem, connecting binary length growth with powers of two, a concept often used in math and simulation style problems.

Recommended for interviews: The bit manipulation approach is the expected answer. Interviewers want to see that you avoid constructing the binary string and instead append bits using shifts. Mentioning the brute-force string approach first shows clear reasoning about the problem, while the optimized shift-based method demonstrates strong understanding of binary representation and time complexity.