Concatenation of Consecutive Binary Numbers

medium math bit modular

Problem

Given n, return the decimal value (mod 1e9+7) of the string formed by concatenating binary representations of 1..n in order.

Inputn = 3

Output27

"1" "10" "11" → "11011" = 27.

def concatenated_binary(n):
    MOD = 10**9 + 7
    ans = 0
    for i in range(1, n + 1):
        ans = ((ans << i.bit_length()) + i) % MOD
    return ans

function concatenatedBinary(n) {
  const MOD = 1000000007n;
  let ans = 0n;
  for (let i = 1; i <= n; i++) {
    const bits = BigInt(32 - Math.clz32(i));
    ans = ((ans << bits) + BigInt(i)) % MOD;
  }
  return Number(ans);
}

class Solution {
    public int concatenatedBinary(int n) {
        long MOD = 1_000_000_007L, ans = 0;
        for (int i = 1; i <= n; i++) {
            int bits = 32 - Integer.numberOfLeadingZeros(i);
            ans = (((ans << bits) % MOD) + i) % MOD;
        }
        return (int) ans;
    }
}

int concatenatedBinary(int n) {
    const long MOD = 1000000007;
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        int bits = 32 - __builtin_clz(i);
        ans = (((ans << bits) % MOD) + i) % MOD;
    }
    return (int) ans;
}

Explanation

We need the number you get by gluing the binary forms of 1, 2, ..., n together. The trick is to do it with bit math rather than building a huge string.

Appending the bits of i to a running number means shifting left to make room and then adding i. The room needed is exactly the number of bits in i, which is i.bit_length().

So each step does ans = ((ans << i.bit_length()) + i) % MOD. Shifting by the bit width slides the existing digits over, the + i drops the new binary block into the freed slots, and the modulo keeps the value from overflowing.

Example: n = 3. Start ans = 0. Add 1 (1 bit) → 1. Add 10 (2 bits) → (1 << 2) + 2 = 6, i.e. 110. Add 11 (2 bits) → (6 << 2) + 3 = 27, i.e. 11011.

That final 27 is the answer, and we got there without ever creating the string "11011".

Time: O(n) Space: O(1)