Concatenation of Consecutive Binary Numbers Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5

Input:
n = 1
Output:
 1
Explanation: "1" in binary corresponds to the decimal value 1.

Example 2:

1
2
3
4
5
6

Input:
n = 3
Output:
 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

1
2
3
4
5
6
7

Input:
n = 12
Output:
 505379714
**Explanation**: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 10^9 + 7, the result is 505379714.

Solution

Method 1 – Bitwise Concatenation and Modulo

Intuition

To efficiently concatenate the binary representations of numbers from 1 to n, we use bitwise operations. For each number, we shift the current result left by the number of bits in the new number and add the new number, taking modulo at each step to avoid overflow.

Approach

  1. Initialize the result to 0 and set the modulo to 10^9 + 7.
  2. For each number from 1 to n:
    • Determine the number of bits required to represent the number.
    • Shift the result left by that number of bits and add the current number.
    • Take modulo after each operation.
  3. Return the final result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int concatenatedBinary(int n) {
        int mod = 1000000007;
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            int bits = Integer.toBinaryString(i).length();
            ans = ((ans << bits) | i) % mod;
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int concatenatedBinary(int n) {
        int mod = 1e9 + 7;
        long long ans = 0;
        for (int i = 1; i <= n; ++i) {
            int bits = 32 - __builtin_clz(i);
            ans = ((ans << bits) | i) % mod;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func concatenatedBinary(n int) int {
    mod := int(1e9 + 7)
    ans := 0
    for i := 1; i <= n; i++ {
        bits := 0
        for x := i; x > 0; x >>= 1 {
            bits++
        }
        ans = ((ans << bits) | i) % mod
    }
    return ans
}
1
2
3
4
5
6
7
8

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        ans = 0
        for i in range(1, n+1):
            bits = i.bit_length()
            ans = ((ans << bits) | i) % mod
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn concatenated_binary(n: i32) -> i32 {
        let modv = 1_000_000_007;
        let mut ans: i64 = 0;
        for i in 1..=n {
            let bits = 32 - (i.leading_zeros() as i32);
            ans = ((ans << bits) | i as i64) % modv;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    concatenatedBinary(n: number): number {
        const mod = 1e9 + 7;
        let ans = 0;
        for (let i = 1; i <= n; i++) {
            const bits = i.toString(2).length;
            ans = ((ans << bits) | i) % mod;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), since each number requires up to log(n) bit operations.
  • 🧺 Space complexity: O(1), only a few variables are used.