Concatenation of Consecutive Binary Numbers
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It iterates from 1 to n, converts each number to its binary string representation, and concatenates these strings. Finally, it converts the resulting long binary string into a decimal number and applies the modulo operation.
Algorithm
- Initialize a
StringBuildersb. - Iterate with a variable
ifrom 1 ton. - For each
i, convert it to a binary string usingInteger.toBinaryString(i). - Append the binary string to
sb. - After the loop, create a
BigIntegerfrom the string insb, specifying base 2. - Calculate the
BigIntegermodulo10^9 + 7. - Return the integer value of the result.
Walkthrough
The core idea is to build the complete binary string first. We use a StringBuilder for efficient string concatenation. A loop runs from i = 1 to n. In each step, Integer.toBinaryString(i) is called to get the binary form of i, which is then appended to the StringBuilder. After the loop, the concatenated binary string can be extremely long, exceeding the capacity of standard primitive types like long. Therefore, we must use java.math.BigInteger to handle the conversion from this binary string to its decimal equivalent. Once we have the BigInteger representation, we can use its mod() method to find the result modulo 10^9 + 7. Finally, we convert the result back to an int.
import java.math.BigInteger; class Solution { public int concatenatedBinary(int n) { StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { sb.append(Integer.toBinaryString(i)); } BigInteger mod = new BigInteger("1000000007"); BigInteger decimalValue = new BigInteger(sb.toString(), 2); return decimalValue.mod(mod).intValue(); }}Complexity
Time
O(N log N). The total length of the string is `S = O(N log N)`. Building this string takes `O(S)`. Converting the string of length `S` to a `BigInteger` and performing the modulo operation also takes time proportional to `S` or more.
Space
O(N log N), where N is the input `n`. The total length of the concatenated binary string is the sum of the bit lengths of numbers from 1 to N, which is approximately `N log N`.
Trade-offs
Pros
Simple and easy to understand.
Directly translates the problem statement into code.
Cons
Highly inefficient for large
n.High memory usage due to the long intermediate string, which can lead to
OutOfMemoryError.BigIntegeroperations are computationally expensive.Likely to result in a "Time Limit Exceeded" error on competitive programming platforms.
This approach avoids building a large string by calculating the decimal value iteratively. For each number i from 1 to n, we update the running total by shifting it left by the number of bits in i and then adding i. This avoids the high memory usage of the brute-force method.
Algorithm
- Initialize a
longvariableresult = 0andMOD = 10^9 + 7. - Iterate with
ifrom 1 ton. - For each
i, calculate its bit length,numBits. For example, by usingInteger.toBinaryString(i).length(). - Update
result:result = ((result << numBits) + i) % MOD. - After the loop, cast the final
resulttointand return.
Walkthrough
The key insight is that concatenating the binary representation of i (which has d bits) to the current result is equivalent to a mathematical operation: new_result = (current_result * 2^d) + i. The term current_result * 2^d is simply current_result left-shifted by d bits (current_result << d). Since the result can become very large, we apply the modulo 10^9 + 7 at each step of the iteration to keep the numbers within the range of a long. The update rule becomes: result = ((result << d) + i) % MOD. In this version of the approach, we calculate the number of bits d for each i by converting i to a string and getting its length.
class Solution { public int concatenatedBinary(int n) { long result = 0; final int MOD = 1_000_000_007; for (int i = 1; i <= n; i++) { // Calculate number of bits for i int numBits = Integer.toBinaryString(i).length(); // Shift the current result left by numBits and add i result = ((result << numBits) % MOD + i) % MOD; } return (int) result; }}Complexity
Time
O(N log N). The main loop runs `N` times. Inside the loop, calculating the number of bits for `i` by converting it to a string takes `O(log i)` time. The total time is the sum of `log i` from `i=1` to `N`, which is `O(N log N)`.
Space
O(1). We only use a constant amount of extra space for variables. (Note: `Integer.toBinaryString` might use temporary space proportional to `log i`, but this is not accumulated).
Trade-offs
Pros
Vastly improved space complexity compared to the brute-force approach.
Avoids
BigInteger, which is slow.Passes within the time limits for the given constraints.
Cons
The time complexity can still be improved.
The repeated calculation of bit length in each iteration is suboptimal.
This is an optimization of the iterative approach. We observe that the number of bits we shift by only increases when the current number i is a power of two. We can leverage this fact to avoid recalculating the bit length in every iteration, leading to an O(N) solution.
Algorithm
- Initialize
long result = 0,int len = 0, andMOD = 10^9 + 7. - Iterate with
ifrom 1 ton. - Inside the loop, check if
iis a power of two using the bitwise trick(i & (i - 1)) == 0. - If it is, increment
len. - Update the result using the current
len:result = ((result << len) + i) % MOD. - After the loop, cast
resulttointand return.
Walkthrough
This approach builds upon the iterative formula: result = ((result << numBits) + i) % MOD. The key optimization is in how we determine numBits. The number of bits in the binary representation of i increases by one only when i is a power of two (e.g., 1, 2, 4, 8, ...). We can maintain a counter for the current number of bits, len. We initialize len = 0. In our loop from i = 1 to n, we first check if i is a power of two. A positive integer i is a power of two if and only if (i & (i - 1)) == 0. If i is a power of two, we increment len. Then, we use the current value of len to perform the shift and update the result: result = ((result << len) + i) % MOD. This avoids the O(log i) work of finding the bit length inside every iteration, reducing the work to a constant-time check.
class Solution { public int concatenatedBinary(int n) { long result = 0; int len = 0; // The number of bits in the current number i final int MOD = 1_000_000_007; for (int i = 1; i <= n; i++) { // Check if i is a power of 2 if ((i & (i - 1)) == 0) { len++; } // Shift the current result left by len and add i result = ((result << len) + i) % MOD; } return (int) result; }}Complexity
Time
O(N). The loop runs `N` times, and all operations inside the loop (bitwise AND, comparison, increment, shift, add, modulo) take constant time.
Space
O(1). We only use a few variables, requiring constant extra space.
Trade-offs
Pros
Optimal time complexity.
Optimal space complexity.
Very fast and efficient for the given constraints.
Cons
The logic, especially the power-of-two check, is more advanced than the more straightforward approaches.
Solutions
Solution
class Solution {public int concatenatedBinary(int n) { final int mod = (int)1 e9 + 7; long ans = 0; for (int i = 1; i <= n; ++i) { ans = (ans << (32 - Integer.numberOfLeadingZeros(i)) | i) % mod; } return (int)ans; }}class Solution {public: int concatenatedBinary(int n) { const int mod = 1e9 + 7; long ans = 0; for (int i = 1; i <= n; ++i) { ans = (ans << (32 - __builtin_clz(i)) | i) % mod; } return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.