Skip to main content

1680 - Concatenation of Consecutive Binary Numbers

Difficulty: Medium | Pattern: Bit Manipulation / Math | Company tags: Amazon

Problem Statement​

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order.

Return the answer modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: "1" → 1

Example 2:

Input: n = 3
Output: 27
Explanation: "1" + "10" + "11" = "11011" → 27

Example 3:

Input: n = 12
Output: 505379714

Approach: Bit Shift — O(n log n)​

Key insight: To append the binary representation of i to our running result, we shift the result left by len(binary(i)) bits, then OR with i. The number of bits in i is i.bit_length().

Algorithm Flow​

def concatenatedBinary(n: int) -> int:
    MOD = 10**9 + 7
    result = 0
    
    for i in range(1, n + 1):
        length = i.bit_length()  # number of bits to shift
        result = ((result << length) | i) % MOD
    
    return result

Optimization: Check Only at Powers of 2​

The bit length of i only changes when i is a power of 2. We can avoid recomputing bit_length() each iteration:

def concatenatedBinary(n: int) -> int:
    MOD = 10**9 + 7
    result = 0
    length = 0
    
    for i in range(1, n + 1):
        if (i & (i - 1)) == 0:  # power of 2: bit length increases
            length += 1
        result = ((result << length) | i) % MOD
    
    return result

Dry Run​

n=3: concatenate "1", "10", "11"

ibitsshift resultOR with iresult
110 shift-left 1 = 00 OR 1 = 11
221 shift-left 2 = 44 OR 2 = 66 ("110")
326 shift-left 2 = 2424 OR 3 = 2727 ("11011")

27 ✓

Complexity​

  • Time: O(n log n) — n iterations, each with O(log i) for bit operations
  • Space: O(1)

Key Terms​

TermDefinition
Bit shift (<<)Shifts all bits of a number left by k positions, equivalent to appending k zero bits — used here to make room for the next number's bits.
bit_length()The minimum number of bits needed to represent an integer in binary (e.g. 5 → 101 → length 3).
Bitwise OR (|)Combines two numbers bit by bit; used to insert i's bits into the freshly shifted space.
Power of two check (i & (i-1) == 0)A bit trick that detects when i is a power of 2, which is exactly when its bit length increases by 1.
Modular arithmeticTaking % MOD at each step to keep numbers bounded, since concatenated binary values grow exponentially.

FAQ​

Q: Why do we need to take the modulo at every step instead of just at the end? A: The concatenated binary number grows exponentially with n and would overflow fixed-size integer types (though Python handles bigints natively, doing it in a language like Java/C++ requires per-step modulo to avoid overflow). Modulo distributes correctly over shift/OR only because we're building the number incrementally.

Q: Why is i.bit_length() the correct shift amount? A: We need to shift the existing result left by exactly the number of bits i occupies so that OR-ing with i places its bits in the newly opened low-order slots without collision.

Q: How does the power-of-two optimization avoid recomputing bit_length()? A: The bit length of i only increases when i crosses a power of 2 (1, 2, 4, 8, ...). Checking i & (i-1) == 0 detects this in O(1), letting us increment a running length counter instead of calling bit_length() (which is also O(1) in Python, but the trick illustrates the underlying bit-length pattern used in other problems).

Q: What if n = 0? A: The loop range(1, n+1) wouldn't execute, so result stays 0. Depending on problem constraints, n >= 1 is usually guaranteed, but it's worth confirming boundary behavior with the interviewer.

Q: Can this be solved with string concatenation instead of bit manipulation? A: Yes — concatenate binary strings of 1..n into one string, then convert with int(s, 2) % MOD. It's simpler to reason about but slower and uses more memory (O(n log n) string length) compared to the O(1)-space bitwise approach.

Quick Revision​

  • Goal: concatenate binary reps of 1..n into one number, mod 1e9+7.
  • Core trick: result = (result << bit_length(i)) | i.
  • Shifting makes room; OR-ing inserts i's bits.
  • Optimization: bit length only changes at powers of 2 — track with i & (i-1) == 0.
  • Apply % MOD every iteration to bound the growing number.
  • Time: O(n log n) naive bit_length calls (or O(n) with the power-of-2 trick); Space: O(1).
  • Dry run for n=3: "1"+"10"+"11" → binary "11011" → decimal 27.
  • No recursion or extra data structures needed — pure iterative bit math.
  • 191 - Number of 1 Bits — same family of bitwise-counting/manipulation problems using shifts and masks.
  • 869 - Reordered Power of 2 — shares reasoning about bit length and powers of 2.
  • Pattern reference: "Bitwise AND of Numbers Range" (LeetCode 201) — another problem centered on reasoning about bit length across a numeric range.