Code Implementation

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        MOD = 10**9 + 7
        result = 0
        length = 0
        for i in range(1, n + 1):
            # If i is a power of 2, increase the bit length
            if (i & (i - 1)) == 0:
                length += 1
            result = ((result << length) | i) % MOD
        return result
      

class Solution {
public:
    int concatenatedBinary(int n) {
        const int MOD = 1e9 + 7;
        long result = 0;
        int length = 0;
        for (int i = 1; i <= n; ++i) {
            if ((i & (i - 1)) == 0) {
                ++length;
            }
            result = ((result << length) | i) % MOD;
        }
        return (int)result;
    }
};
      

class Solution {
    public int concatenatedBinary(int n) {
        final int MOD = 1_000_000_007;
        long result = 0;
        int length = 0;
        for (int i = 1; i <= n; ++i) {
            if ((i & (i - 1)) == 0) {
                ++length;
            }
            result = ((result << length) | i) % MOD;
        }
        return (int) result;
    }
}
      

var concatenatedBinary = function(n) {
    const MOD = 1e9 + 7;
    let result = 0;
    let length = 0;
    for (let i = 1; i <= n; ++i) {
        if ((i & (i - 1)) === 0) {
            ++length;
        }
        result = ((result << length) | i) % MOD;
    }
    return result;
};
      

Problem Description

Given a positive integer n, you are to concatenate the binary representations of all numbers from 1 to n in order, and interpret the resulting binary string as a decimal number. Return this number modulo 10^9 + 7.

For example, if n = 3:

• Binary representations: 1 (1), 2 (10), 3 (11)
• Concatenated: 11011
• Decimal value: 27
• Return: 27

• 1 <= n <= 105
• Return the answer modulo 10^9 + 7

Thought Process

The naive approach is to convert each number from 1 to n to its binary string, concatenate all these strings, and then convert the final string to an integer. However, this approach is not efficient for large n because the concatenated string can be extremely large (up to hundreds of thousands of bits).

To optimize, we need to avoid building huge strings and instead work directly with numbers and bit operations. The key insight is that concatenating a new number's binary representation to the right of an existing binary number is equivalent to shifting the existing number left by the length of the new binary, and then adding the new number.

We also need to keep the result modulo 10^9 + 7 at every step to prevent integer overflow.

Solution Approach

• We initialize a variable result to 0 to keep the ongoing concatenated value.
• We iterate from 1 to n:
• For each number i, determine the length of its binary representation. This can be done by checking if i is a power of two (since the number of bits increases by 1 only at powers of two).
• Shift result left by the number of bits in i (equivalent to multiplying by 2^{length}), then add i.
• Take modulo 10^9 + 7 at each step.
• After the loop, return result.

Using bit manipulation and modular arithmetic allows us to efficiently compute the answer without ever building a full binary string.

Example Walkthrough

Let's walk through the process for n = 3:

• Step 1: i = 1
  • Binary: 1 (1 bit)
  • Shift result (0) left by 1: 0
  • Add 1: 1
• Step 2: i = 2
  • Binary: 10 (2 bits, because 2 is a power of two)
  • Shift result (1) left by 2: 100 (binary) = 4 (decimal)
  • Add 2: 110 (binary) = 6 (decimal)
• Step 3: i = 3
  • Binary: 11 (still 2 bits)
  • Shift result (6) left by 2: 11000 (binary) = 24 (decimal)
  • Add 3: 11011 (binary) = 27 (decimal)

Time and Space Complexity

• Brute-force approach:
  • Time: O(N log N), where converting each number to binary and concatenating strings takes O(log N) per number.
  • Space: O(N log N), since the concatenated string can be up to O(N log N) bits long.
• Optimized approach (bit manipulation):
  • Time: O(N), since each number is processed in constant time (bit length is at most log N, but we only increment when needed).
  • Space: O(1), since we only keep a few integer variables and never build the full string.

Summary

By recognizing that concatenating binary numbers is equivalent to shifting and OR-ing, we avoid expensive string operations and keep the computation efficient. The key insight is to update the bit length only when we hit a power of two, and to use modular arithmetic at every step. This makes the solution both elegant and highly efficient, scaling easily to large values of n.