Problem Statement

Given an integer n, concatenate the binary representation of numbers from 1 to n and return the decimal value modulo 10⁹ + 7.

Example

1 → 1
2 → 10
3 → 11

Core Intuition

Binary concatenation can be simulated using bit shifting.

• Left shift the current result to create space
• Add the current number

result = (result << bitLength) + i

Key Optimization

The bit length increases only when the number is a power of 2.

(i & (i - 1)) == 0

This helps track how many bits to shift efficiently.

Java Implementation

class Solution {
    public int concatenatedBinary(int n) {
        long result = 0;
        int mod = 1_000_000_007;
        int bitLength = 0;

        for (int i = 1; i <= n; i++) {

            if ((i & (i - 1)) == 0) {
                bitLength++;
            }

            result = ((result << bitLength) + i) % mod;
        }

        return (int) result;
    }
}

Complexity Analysis

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

Watch Full Video Explanation