🔗 Beginner-Friendly Guide 'Concatenation of Consecutive Binary Numbers' - Problem 1680 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

You’re given:
An integer n, representing a range of numbers starting from 1 up to n.

Your goal:
Concatenate the binary representations of every number in that range in order. Convert the resulting binary string back into a decimal integer and return the result modulo (10^9 + 7).

Intuition: The Art of Shifting

To solve this without actually creating a massive string (which would be slow and memory‑heavy), we use bitwise math.

For every number i from 1 to n:

1. Find the bit length: Determine how many bits are needed to represent i.
   Example: 2 is 10 in binary, which needs 2 bits.
2. Shift the result: Shift the current total left by that many bits, creating a “slot” for the new value.
3. Merge with OR: Use the bitwise OR operator to place the bits of i into the new slot.
4. Keep it small: Apply the modulo (10^9 + 7) at every step to prevent overflow.

Walkthrough: Understanding the Example

For n = 3:

The final binary 11011 equals 27 in decimal.

C++ Solution

#include 

class Solution {
public:
    const int mod = 1e9 + 7;

    int concatenatedBinary(int n) {
        long result = 0;
        for (int i = 1; i (result);
    }
};

Python Solution

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        mod = 10**9 + 7
        result = 0

        for i in range(1, n + 1):
            # bit_length() gives the number of bits required for the integer
            width = i.bit_length()
            # Shift result left by width and add the current number i
            result = ((result << width) | i) % mod

        return result

JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var concatenatedBinary = function(n) {
    const mod = 1000000007n;
    let result = 0n;

    for (let i = 1; i <= n; i++) {
        // Find bit length by converting to binary string
        let width = BigInt(i.toString(2).length);
        // Using BigInt to handle large numbers before modulo
        result = ((result << width) | BigInt(i)) % mod;
    }

    return Number(result);
};

Key Takeaways

• Bitwise Shifting: Shifting left by k bits is equivalent to multiplying a number by (2^k).
• Modulo Arithmetic: Applying the modulo at each step keeps values within safe limits of the data type.
• Efficiency: Calculating bit width and using bitwise operations is significantly faster than string concatenation and conversion.

Final Thoughts

This problem illustrates how “low‑level” thinking can lead to high‑performance solutions. In real‑world scenarios, such concepts are vital for data compression and network protocols, where information is packed into the smallest possible bit‑space to save bandwidth. Mastering bitwise logic makes you a more versatile developer, especially when working close to the hardware or optimizing high‑traffic systems.