0521MediumMathBit ManipulationSimulation

Serial Number From Stacked Bit Patterns

Tracked in this browser only

Trains the technique from

LeetCode 1680Concatenation of Consecutive Binary Numbers

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def concatenated_binary(n: int) -> int:

Java

public int concatenatedBinary(int n)

The intended approach

Time O(n): one shift, one or, and one reduction per number.Space O(1) beyond the returned value.

Keep the serial for the numbers seen so far and extend it one number at a time. Appending `i` means sliding the running value left by the number of bits `i` occupies and then filling that gap with `i` itself, which is a shift followed by a bitwise or. The bit width only grows when `i` reaches the next power of two, so a single counter tracks it without recomputing anything, and the reduction is applied on every step to keep the value small.

Pythonentry point: concatenated_binary

def concatenated_binary(n):
    # O(n) time, O(1) space: shift the running value left by exactly as many
    # bits as the next number needs, then drop the next number into the gap.
    MOD = 1000000007
    value = 0
    width = 0
    power = 1
    for i in range(1, n + 1):
        if i == power:
            width += 1
            power *= 2
        value = ((value << width) | i) % MOD
    return value

The obvious version

Spell the bit pattern of every number out as text by repeated halving, join the pieces, hand the whole string to a base-two parser and reduce the result once at the end.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_concatenated_binary(n):
    MOD = 1000000007
    pieces = []
    for i in range(1, n + 1):
        bits = ""
        j = i
        while j:
            bits = ("1" if j & 1 else "0") + bits
            j >>= 1
        pieces.append(bits)
    return int("".join(pieces), 2) % MOD

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in