Concatenation of Consecutive Binary Numbers - Solution & Explanation
Problem Statement
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:
Input: n = 1 Output: 1 Explanation: "1" in binary corresponds to the decimal value 1.
Example 2:
Input: n = 3 Output: 27 Explanation: 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 Explanation: The concatenation results in "1101110010111011110001001101010111100". The decimal value of that is 118505380540. After modulo 109 + 7, the result is 505379714.
Constraints:
1 <= n <= 105
Approach Overview
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.
Approach 1: Bit Manipulation
This method leverages bit manipulation to efficiently construct the resulting number without physically concatenating binary strings. As each integer from 1 to n is processed, its binary representation is appended using bitwise operations, which helps avoid the overhead of string manipulation.
In this implementation, a loop iterates through each number from 1 to n. When the loop reaches a new power of 2, the binary length of numbers increases by one. Using left shift operations, we append the current number, then apply the modulo operation to keep the result manageable.
Code
Python
Java
C++
C
JavaScript
C#
Go
TypeScript
Rust
Complexity
Time Complexity: O(n), because we process each number from 1 to n.
Space Complexity: O(1), as we use a fixed amount of additional space.
Approach 2: Binary String Accumulation
This naive strategy involves directly constructing the final binary string representation step by step. After forming the complete string, it converts it to an integer and performs modulo operation. This approach might be less efficient for large n due to string operations being costly.
This approach builds a complete string of concatenated binary representations of numbers from 1 to n, converts it to integer, and applies modulo.
Complexity
Time Complexity: O(n * log n), as string operations for binary conversions dominate computation time.
Space Complexity: O(n * log n), due to the storage of the growing binary string.
Approach 3: 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 shift to record the current number of bits to shift. When i is a power of 2, shift needs to be incremented by 1.
The time complexity is O(n), where n is the given integer. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Bit Manipulation | Time Complexity: O(n), because we process each number from 1 to n. Space Complexity: O(1), as we use a fixed amount of additional space. |
| Binary String Accumulation | Time Complexity: O(n * log n), as string operations for binary conversions dominate computation time. Space Complexity: O(n * log n), due to the storage of the growing binary string. |
| Bit Manipulation (Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary String Accumulation | O(n log n) | O(n log n) | Conceptual or brute-force implementation when constraints are small and clarity is preferred. |
| Bit Manipulation with Left Shift | O(n) | O(1) | Optimal solution for large n. Avoids building strings and appends binary digits using shifts. |
Video Solution
Concatenation of Consecutive Binary Numbers | Leetcode #1680 • Techdose • 8,401 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Concatenation of Consecutive Binary Numbers easy or hard?
Concatenation of Consecutive Binary Numbers Python/Java solution
How to solve Concatenation of Consecutive Binary Numbers in O(n)?
What is the best approach for Concatenation of Consecutive Binary Numbers?
Is Concatenation of Consecutive Binary Numbers asked at Google/Amazon/Meta?
What data structure is used in Concatenation of Consecutive Binary Numbers?
What is the time complexity of Concatenation of Consecutive Binary Numbers?
Ready to solve this problem?
Practice Concatenation of Consecutive Binary Numbers with our built-in code editor and test cases.
Practice on FleetCode