Solution Explanation for Concatenation of Consecutive Binary Numbers

This problem asks to find the decimal value of the binary string formed by concatenating the binary representations of numbers from 1 to n, modulo 109 + 7. A naive approach would involve converting each number to its binary representation, concatenating them, and then converting the resulting binary string back to decimal. However, this is inefficient for large n.

The optimal solution uses bit manipulation for efficiency. The core idea is to iteratively build the concatenated binary string by shifting the existing result to the left and adding the next number's binary representation.

Algorithm:

1. Initialization: Initialize ans to 0. This variable will store the decimal value of the concatenated binary string. We also initialize mod to 109 + 7 for the modulo operation.

2. Iteration: Iterate from i = 1 to n.

3. Bit Length: Determine the number of bits (bit_length) in the current number i. This is efficiently done using i.bit_length() in Python, Integer.numberOfLeadingZeros(i) in Java, __builtin_clz(i) in C++, or bits.Len(uint(i)) in Go. These functions count the number of leading zeros, which, when subtracted from 32 (for 32-bit integers) gives the number of significant bits. Note that this is equivalent to finding the position of the most significant set bit in i.

4. Shift and Add: Left-shift the current ans by bit_length bits (ans << bit_length). This makes space for the binary representation of i. Then, perform a bitwise OR operation (| i) to add i to the end. Finally, take the modulo with mod to prevent integer overflow.

5. Return: After the loop completes, ans holds the final decimal value modulo 109 + 7.

Time Complexity: O(n). The loop iterates n times. Each operation within the loop (bit length calculation, shift, OR, modulo) takes constant time.

Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Examples (with slight variations based on language features):

Python:

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

Java:

class Solution {
    public int concatenatedBinary(int n) {
        final int mod = (int) 1e9 + 7;
        long ans = 0; // Use long to avoid potential overflow before modulo
        for (int i = 1; i <= n; ++i) {
            ans = (ans << (Integer.SIZE - Integer.numberOfLeadingZeros(i)) | i) % mod;
        }
        return (int) ans;
    }
}

C++:

class Solution {
public:
    int concatenatedBinary(int n) {
        long long ans = 0; // Use long long to avoid potential overflow before modulo
        long long mod = 1e9 + 7;
        for (int i = 1; i <= n; i++) {
            ans = (ans << (32 - __builtin_clz(i)) | i) % mod;
        }
        return (int)ans;
    }
};

Go:

import (
	"math/bits"
)
 
func concatenatedBinary(n int) int {
	ans := 0
	mod := int(1e9 + 7)
	for i := 1; i <= n; i++ {
		ans = (ans<<bits.Len(uint(i)) | i) % mod
	}
	return ans
}

These codes all implement the same core algorithm, with minor syntax and function name differences to account for language-specific features. The use of long or long long in Java and C++ respectively is crucial to prevent potential integer overflow before applying the modulo operation. The Go solution uses the math/bits package for efficient bit manipulation. Each solution effectively achieves the desired result with O(n) time and O(1) space complexity.