Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Appending an integer's binary representation means shifting the existing value left by that integer's bit length, then filling the new low bits. We need only the concatenation modulo the required modulus, because this arithmetic update preserves congruence.

Approach

Visit integers from one through n. Determine each integer's bit length by repeatedly shifting a temporary copy right. Shift the running result left by that length, combine the integer with bitwise OR, and reduce modulo 10^9 + 7. The shifted result has zero low bits, so OR is equivalent to addition here. Return the final remainder. The reference implementations recompute each bit length rather than updating it only at powers of two.

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        MOD = 10**9 + 7
        res = 0

        def bits(n):
            b = 0

            while n:
                b += 1
                n >>= 1

            return b

        for curr in range(1, n + 1):
            res <<= bits(curr)
            res = (res | curr) % MOD

        return res

Complexity analysis

Let B = floor(log2(n)) + 1. Both displayed implementations recompute every current integer's bit length with repeated exact-integer right shifts. In the word-RAM model this is O(nB) = O(n log n) time and O(1) auxiliary space in machine words. Under strict immutable arbitrary-precision costs, it is up to O(nB^2) = O(n log^2 n) bit time with O(B) = O(log n) auxiliary bit space.