Concatenation of Consecutive Binary Numbers

Concatenation of Consecutive Binary Numbers - Problem

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

For example, if n = 3, the binary representations are:

1 → "1"
2 → "10"
3 → "11"

Concatenating them gives "11011", which is 27 in decimal.

Input & Output

Example 1 — Basic Case

$ Input: n = 1

› Output: 1

💡 Note: Only number 1 has binary representation "1", so result is 1 in decimal

Example 2 — Small Range

$ Input: n = 3

› Output: 27

💡 Note: Binary: 1→"1", 2→"10", 3→"11". Concatenated: "11011" = 16+8+2+1 = 27

Example 3 — Power of 2

$ Input: n = 4

› Output: 220

💡 Note: Binary: 1→"1", 2→"10", 3→"11", 4→"100". Concatenated: "1101110" = 128+64+8+4+2 = 220

Constraints

1 ≤ n ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Integer n = 3

Process

Convert 1,2,3 to binary and concatenate

Output

Decimal value of concatenated binary string

Key Takeaway

🎯 Key Insight: Use bit shifting to avoid string operations and efficiently build the decimal result

Asked in

f Facebook 15 G Google 12 a Amazon 8

The key insight is to use bit shifting to build the result incrementally instead of string concatenation. For each number i, shift the current result left by the number of bits in i, then add i. Best approach is Bit Shifting Optimization. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Bit Shifting Optimization	O(n log n)	O(1)	Use bit operations to build result incrementally without string concatenation
String Concatenation	O(n log n)	O(n log n)	Convert each number to binary string, concatenate all, convert final string to decimal

Bit Shifting Optimization — Algorithm Steps

Initialize result = 0
For each number i from 1 to n:
Calculate bits needed for i (log₂(i) + 1)
Shift result left by that many bits
Add i to result
Take modulo at each step

Visualization

Tap to expand

Step-by-Step Walkthrough

Process i=1

result = 0, shift left 1 bit, add 1 → result = 1

Process i=2

result = 1, shift left 2 bits, add 2 → result = 6

Process i=3

result = 6, shift left 2 bits, add 3 → result = 27

Code -

solution.c — C

#include <stdio.h>
#include <math.h>

int solution(int n) {
    const int MOD = 1000000007;
    long long result = 0;
    
    for (int i = 1; i <= n; i++) {
        // Calculate number of bits in i
        int bits = (int)log2(i) + 1;
        // Shift result left by 'bits' positions and add i
        result = ((result << bits) + i) % MOD;
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

For each of n numbers, we calculate bit length (O(log i)) and perform bit operations

⚡ Linearithmic

Space Complexity

O(1)

Only use a few variables, no additional data structures

✓ Linear Space

42.5K Views

Medium Frequency

~25 min Avg. Time

786 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Shifting Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler