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

Problem Summary ## Intuition: The Art of Shifting ## Walkthrough: Understanding the Examples ## C++ Solution ## Python Solution ## JavaScript Solution ## Key Takeaways ## Final Thoughts 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. 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$. 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: Let's look at $n = 3$: The final binary 11011 converts to 27 in decimal. 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. Templates let you quickly answer FAQs or store snippets for re-use. Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink. Hide child comments as well For further actions, you may consider blocking this person and/or reporting abuse CODE_BLOCK: #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 CODE_BLOCK: #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; } }; CODE_BLOCK: #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; } }; COMMAND_BLOCK: 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 COMMAND_BLOCK: 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 COMMAND_BLOCK: 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 CODE_BLOCK: /** * @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 CODE_BLOCK: /** * @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); }; CODE_BLOCK: /** * @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); }; - 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. - 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. - Merge with OR: Use the bitwise OR operator to place the bits of $i$ into that new slot. - Keep it small: Since the number grows incredibly fast, we apply the modulo $10^9 + 7$ at every single step to prevent integer overflow. - 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. - 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.