Concatenation of Consecutive Binary Numbers
Real-world version: Serial Number From Stacked Bit PatternsThe statement here is our own: the same inputs, outputs and technique.
A programmer burns a serial number into a chip as follows. Take the counting numbers 1, 2, 3, ..., n in order. Write each one in base two, with no leading zeros, and lay the bit patterns end to end with nothing between them. The whole run of bits is then read as a single base-two number, and that is the serial.
Given n, return the serial reduced modulo 1000000007.
Examples
Example 1
- Input
- n = 5
- Output
- 1765
The bit patterns are 1, 10, 11, 100 and 101. Laid end to end they read 11011100101, and that base-two number is 1765.
Example 2
- Input
- n = 8
- Output
- 1808248
Appending the pattern 1000 to the run built for the first seven numbers gives a base-two number equal to 1808248, which is already below the divisor.
Example 3
- Input
- n = 900
- Output
- 367197511
The run of bits for the first 900 numbers is far past 30 bits long, so the reported value is the reduction of that number modulo 1000000007.
Constraints
- 1 <= n <= 10^5
- The answer is the serial reduced modulo 1000000007, so it is below 10^9 + 7.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def concatenated_binary(n: int) -> int:public int concatenatedBinary(int n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's