Concatenation of consecutive binary numbers

Math Bit Manipulation Simulation

66.4% acceptance

Feb 25, 2026

1756

447

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10^9+7.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn concatenated_binary(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut res: i64 = 0;
    for i in 1..=n as i64 {
      // Number of bits in i
      let bits = i64::BITS - i.leading_zeros();
      res = ((res << bits) | i) % MOD;
    }
    res as i32
  }
}