DEV Community

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

Posted on

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

#programming #cpp #javascript #python

Ever wondered how computers handle massive strings of data by simply stitching bits together? This problem challenges you to simulate that exact process by joining the binary forms of consecutive numbers into one giant value. It is a fantastic exercise in bitwise manipulation and understanding how large numbers are stored in memory.

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. You must then convert that resulting binary string back into a decimal integer, returning 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. Think of it like a conveyor belt. When you want to add a new number to the end of your current binary sequence, you first need to make exactly enough "room" for it.

For every number $i$ from 1 to $n$, we follow these steps:

  1. Find the bit length: Determine how many bits are needed to represent the current number $i$. For example, the number 2 is 10 in binary, which needs 2 bits.
  2. Shift the result: Shift our existing total to the left by that many bits. This effectively adds zeros to the end of our current number, creating a "slot" for the new value.
  3. Merge with OR: Use the bitwise OR operator to place the bits of $i$ into that new slot.
  4. Keep it small: Since the number grows incredibly fast, we apply the modulo $10^9 + 7$ at every single step to prevent integer overflow.

Walkthrough: Understanding the Examples

Let's look at $n = 3$:

  • Step 1 ($i = 1$): Binary is 1. Result becomes 1.
  • Step 2 ($i = 2$): Binary is 10 (2 bits). We shift our current result (1) left by 2 positions to get 100. We then OR it with 10 to get 110. Decimal value: 6.
  • Step 3 ($i = 3$): Binary is 11 (2 bits). We shift our current result (110) left by 2 positions to get 11000. We then OR it with 11 to get 11011.

The final binary 11011 converts to 27 in decimal.

C++ Solution 

#include <bit>

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

    int concatenatedBinary(int n) {
        long result = 0;
        for (int i = 1; i <= n; ++i) {
            // std::bit_width calculates the number of bits required for i
            int width = std::bit_width((unsigned)i);
            result = ((result << width) | i) % mod;
        }
        return (int)result;
    }
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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);
};
Enter fullscreen mode Exit fullscreen mode

Key Takeaways

  • Bitwise Shifting: Shifting left by $k$ bits is mathematically equivalent to multiplying a number by $2^k$.
  • Modulo Arithmetic: When working with large numbers, applying modulo at each step of an addition or multiplication keeps the values within the safe limits of your data type.
  • Efficiency: Calculating bit width and using bitwise operations is significantly faster than performing string concatenation and converting back to an integer.

Final Thoughts

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

Top comments (0)