Concatenate the binary representations of 1 through n in order and return the value modulo .
Concatenation of Consecutive Binary Numbers
Given a positive integer n, write down the binary representation of every integer from 1 to n in increasing order, concatenate them into one long binary string, and interpret that string as a binary number.
Return the decimal value of that number modulo .
For example, if n = 3, the sequence of binaries is 1, 10, 11, and the concatenation is 11011, which equals 27 in decimal.
Input Format
- A single integer
n. - The task is to process all integers from
1tonin order.
Output Format
- Return one integer: the decimal value of the concatenated binary string modulo .
Constraints
- .
- The answer should be computed modulo .
- Use an approach that is efficient enough for large
n. - The binary representation of each number has no leading zeros.
Example 1
Input
n = 3
Output
27
Explanation
Binary strings are 1, 10, and 11. Concatenating them gives 11011, which is 27 in decimal.
Example 2
Input
n = 12
Output
505379714
Explanation
Concatenating binaries from 1 to 12 produces a very large binary number. After taking modulo , the result is 505379714.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.