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 <= 105This 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.
Java
C++
C
JavaScript
C#
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.
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.
Java
C++
C
JavaScript
C#
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 | 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. |
Concatenation of Consecutive Binary Numbers | Leetcode #1680 • Techdose • 7,887 views views
Watch 9 more video solutions →Practice Concatenation of Consecutive Binary Numbers with our built-in code editor and test cases.
Practice on FleetCode