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.
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; }}Video 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.