LeetCode 1680 - Concatenation of Consecutive Binary Numbers

The problem asks us to build a very large binary number by concatenating the binary representations of every integer fro

leetcodemediummathbit-manipulationsimulation

LeetCode Problem 1680

Difficulty: 🟡 Medium
Topics: Math, Bit Manipulation, Simulation

Solution

Problem Understanding

The problem asks us to build a very large binary number by concatenating the binary representations of every integer from 1 through n, in order, and then return its decimal value modulo 10^9 + 7.

For example, if n = 3:

  • 1 in binary is "1"
  • 2 in binary is "10"
  • 3 in binary is "11"

Concatenating them produces:

"1" + "10" + "11" = "11011"

The binary string "11011" equals 27 in decimal, so the answer is 27.

The important detail is that we are not asked to return the binary string itself. Instead, we must compute its decimal value efficiently.

The constraint 1 <= n <= 10^5 is critical. A naive implementation that literally builds the binary string would eventually create a string with hundreds of thousands of characters. Converting that huge string back into an integer would also be expensive and unnecessary.

The problem guarantees that n is always at least 1, so we do not need to handle empty input cases. However, there are still important implementation concerns:

  • The concatenated value grows extremely quickly, so integer overflow becomes an issue in languages with fixed integer sizes.
  • Constructing the full binary string wastes memory.
  • We must apply modulo 10^9 + 7 continuously during computation.

The key challenge is finding a way to simulate binary concatenation mathematically without actually building the enormous binary string.

Approaches

Brute Force Approach

The most direct solution is:

  1. Convert every number from 1 to n into binary.
  2. Append each binary string to a growing result string.
  3. Convert the final binary string into a decimal integer.
  4. Return the value modulo 10^9 + 7.

This approach is conceptually simple because it follows the problem statement literally.

For example, if n = 5:

1  -> "1"
2  -> "10"
3  -> "11"
4  -> "100"
5  -> "101"

Concatenated:
"11011100101"

After building the full string, we could parse it as a binary integer.

The issue is efficiency. The total binary length grows roughly as:

$$O(n \log n)$$

For n = 100000, the resulting binary string becomes extremely large. String concatenation and big integer conversion become expensive operations.

Although this might barely work in some high level languages with optimized big integers, it is not the intended solution and is inefficient in both memory and runtime.

Optimal Approach

The key observation is that concatenating binary numbers can be simulated using bit shifting.

Suppose our current accumulated value is:

result

and we want to append the binary representation of some number x.

Appending binary digits is equivalent to:

  1. Shift result left by the number of bits in x
  2. Add x

Mathematically:

$$result = (result \ll bits) + x$$

For example:

result = binary "11011" = 27
x = binary "100" = 4

Appending "100" means:

"11011" -> "11011100"

Shifting left by 3 bits:

27 << 3 = 216

Then add 4:

216 + 4 = 220

Binary of 220:

11011100

Exactly what we wanted.

The remaining challenge is determining how many bits each number requires.

A number gains a new binary digit whenever it becomes a power of two:

1   -> 1 bit
2   -> 2 bits
4   -> 3 bits
8   -> 4 bits
16  -> 5 bits

So whenever x is a power of two, we increment our bit length counter.

This gives an elegant linear time solution with constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n log n) Builds the entire binary string explicitly
Optimal O(n) O(1) Uses bit shifting to simulate concatenation

Algorithm Walkthrough

  1. Initialize a variable result = 0.

This variable stores the decimal value of the concatenated binary sequence processed so far. 2. Initialize bit_length = 0.

This tracks how many binary digits the current number requires. 3. Iterate through all integers num from 1 to n.

For each number, we append its binary representation to the accumulated result. 4. Check whether num is a power of two.

A number is a power of two if:

$$num & (num - 1) = 0$$

This works because powers of two contain exactly one set bit in binary. 5. If num is a power of two, increment bit_length.

This means we now need one additional binary digit for all numbers in this range. 6. Shift result left by bit_length.

Left shifting creates enough empty binary positions to append the new number. 7. Add num to the shifted value.

This effectively concatenates the binary digits of num. 8. Apply modulo 10^9 + 7.

This prevents overflow and keeps the number manageable. 9. After processing all numbers, return result.

Why it works

At every iteration, result stores the exact decimal value of the concatenated binary string formed from 1 through num - 1.

When processing num, shifting left by its bit length creates exactly enough empty binary positions to append the new binary digits. Adding num fills those positions with the correct bits.

Because this invariant holds at every step, the final value is the decimal representation of the full concatenated binary sequence.

Python Solution

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        MOD = 10**9 + 7
        
        result = 0
        bit_length = 0
        
        for num in range(1, n + 1):
            if (num & (num - 1)) == 0:
                bit_length += 1
            
            result = ((result << bit_length) + num) % MOD
        
        return result

The implementation starts by defining the modulo constant 10^9 + 7, since the result can grow extremely large.

The variable result stores the decimal value of the concatenated binary sequence processed so far.

The variable bit_length tracks how many bits are required to represent the current number. Instead of recomputing this with logarithms or string conversion, the code updates it only when the current number is a power of two.

Inside the loop, the condition:

(num & (num - 1)) == 0

checks whether num is a power of two. If it is, the binary representation length increases by one.

The core operation is:

result = ((result << bit_length) + num) % MOD

The left shift creates space for the new binary digits, and adding num appends those digits.

Modulo is applied immediately after every update to avoid large intermediate values.

Go Solution

func concatenatedBinary(n int) int {
    const MOD int = 1000000007

    result := 0
    bitLength := 0

    for num := 1; num <= n; num++ {
        if (num & (num - 1)) == 0 {
            bitLength++
        }

        result = ((result << bitLength) + num) % MOD
    }

    return result
}

The Go implementation follows the exact same logic as the Python solution.

One important consideration in Go is integer overflow. Since intermediate values can become large, applying modulo during every iteration is essential.

Go integers are fixed width, unlike Python's arbitrary precision integers. However, because we reduce modulo 10^9 + 7 after every operation, standard integer arithmetic remains safe for this problem.

Worked Examples

Example 1

Input:

n = 1
num Binary bit_length result before result after
1 1 1 0 1

Final answer:

1

Example 2

Input:

n = 3
num Binary bit_length Operation result
1 1 1 (0 << 1) + 1 1
2 10 2 (1 << 2) + 2 6
3 11 2 (6 << 2) + 3 27

Binary progression:

1
110
11011

Final answer:

27

Example 3

Input:

n = 12
num Binary bit_length result after step
1 1 1 1
2 10 2 6
3 11 2 27
4 100 3 220
5 101 3 1765
6 110 3 14126
7 111 3 113015
8 1000 4 1808248
9 1001 4 28931977
10 1010 4 462911642
11 1011 4 406586234
12 1100 4 505379714

Final answer:

505379714

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each number from 1 to n is processed once
Space O(1) Only a few integer variables are used

The algorithm performs a constant amount of work per iteration. The power of two check, left shift, addition, and modulo operation are all constant time operations.

No auxiliary data structures are created, and the algorithm never stores the actual concatenated binary string, so the extra space usage remains constant.

Test Cases

solution = Solution()

assert solution.concatenatedBinary(1) == 1
# Smallest valid input

assert solution.concatenatedBinary(3) == 27
# Basic example from prompt

assert solution.concatenatedBinary(12) == 505379714
# Larger example with modulo behavior

assert solution.concatenatedBinary(2) == 6
# "110" in binary equals 6

assert solution.concatenatedBinary(4) == 220
# Tests transition to a new bit length

assert solution.concatenatedBinary(5) == 1765
# Verifies continued concatenation after bit-length increase

assert solution.concatenatedBinary(7) == 113015
# Last number before another power-of-two boundary

assert solution.concatenatedBinary(8) == 1808248
# Tests another bit-length transition

assert solution.concatenatedBinary(100000) >= 0
# Stress test for upper constraint
Test Why
n = 1 Validates smallest possible input
n = 3 Verifies basic concatenation logic
n = 12 Confirms modulo handling
n = 2 Tests simple multi-number concatenation
n = 4 Checks power-of-two boundary behavior
n = 5 Ensures bit length remains correct after transition
n = 7 Tests values immediately before next power of two
n = 8 Validates another bit-length increase
n = 100000 Stress test for maximum constraint

Edge Cases

One important edge case is the smallest possible input, n = 1. In this scenario, the algorithm only processes a single number. The implementation correctly initializes bit_length to 1 when encountering the first power of two and returns 1 immediately after the first iteration.

Another critical edge case occurs at powers of two such as 2, 4, 8, and 16. These numbers require one additional binary digit compared to the previous numbers. Forgetting to update the bit length at these boundaries would produce incorrect concatenation results because the left shift would not create enough space for the appended bits. The implementation handles this correctly using the power-of-two check:

(num & (num - 1)) == 0

A third important edge case involves very large values of n, especially near the upper constraint 100000. The concatenated binary number becomes astronomically large, far exceeding standard integer sizes. A naive solution that constructs the actual binary string could consume excessive memory and runtime. This implementation avoids that entirely by maintaining only the current modular value and never storing the full binary representation.

Another subtle edge case is integer overflow in fixed-width languages like Go. Repeated shifting and addition can easily exceed 32-bit integer limits. Applying modulo during every iteration keeps intermediate values bounded and ensures correctness throughout the computation.