Concatenation of Consecutive Binary Numbers

Concatenation of Consecutive Binary Numbers

What is this problem about?

The Concatenation of Consecutive Binary Numbers coding problem asks you to take all integers from 1 to n, convert them to their binary string representations, and concatenate these strings in order. You then need to return the decimal value of the resulting large binary string, modulo 10^9 + 7. For example, if n=3, the binary strings are "1", "10", and "11". Concatenated, they form "11011", which is 27 in decimal.

Why is this asked in interviews?

Amazon uses this Bit Manipulation interview pattern to test your ability to work with bitwise operations and large numbers. It evaluates if you can identify a mathematical way to "shift" and "add" numbers without actually converting them to strings, which would be extremely slow and memory-intensive.

Algorithmic pattern used

The problem is solved using Iterative Bit Shifting and Modular Arithmetic. For each number i from 1 to n:

1. Calculate the number of bits in i. Let's call it len.
2. Shift the current result to the left by len bits: res = res << len.
3. Add i to the result: res = (res + i) % modulo. The key is to update the "shift length" only when i reaches a new power of 2.

Example explanation

n = 3

1. i = 1: Binary is 1 (1 bit). Result = 1.
2. i = 2: Binary is 10 (2 bits).
   • Shift result (1) left by 2: 100 (binary) = 4 (decimal).
   • Add i (2): 4 + 2 = 6. (Binary 110).
3. i = 3: Binary is 11 (2 bits).
   • Shift result (6) left by 2: 11000 (binary) = 24 (decimal).
   • Add i (3): 24 + 3 = 27. (Binary 11011). Result: 27.

Common mistakes candidates make

• String Concatenation: Using strings to build the binary sequence, which will cause a memory overflow or time out for large n.
• Modulo at the end: Waiting until the very end to apply the modulo. The concatenated number will be massive and exceed 64-bit limits almost immediately.
• Bit length calculation: Re-calculating the bit length of i using log2 in every loop, which can be slow and prone to precision errors. A simple bit check is better.

Interview preparation tip

Practice using (i & (i - 1)) == 0 to detect when a number is a power of 2. This is a very common trick in bit manipulation problems to know when you need to increment your "bit length" counter.