Concatenation of Consecutive Binary Numbers

Medium
430.

Concatenation of Consecutive Binary Numbers

Concatenation of Consecutive Binary Numbers is a medium coding problem on math, bit manipulation and simulation, asked in Amazon and Google interviews.

Given an integer n, concatenate the binary representations of 1 through n into one binary string and return its decimal value modulo 10^9 + 7.

Example 1

Input
n = 1
Output
1

Example 2

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

Example 3

Input
n = 12
Output
505379714

Constraints

  • 1 <= n <= 300
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var concatenatedBinary = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Concatenation of Consecutive Binary Numbers — Solution

Concatenation of Consecutive Binary Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Concatenation of Consecutive Binary Numbers is a medium coding problem on math, bit manipulation and simulation, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Math, Bit Manipulation, Simulation
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer n, concatenate the binary representations of 1 through n into one binary string and return its decimal value modulo 10^9 + 7.

Example 1

Input: n = 1
Output: 1

Example 2

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

Example 3

Input: n = 12
Output: 505379714

Constraints

  • 1 <= n <= 300

Hints for Concatenation of Consecutive Binary Numbers

  1. Hint 1

    Building the string explicitly overflows fast — keep a running value modulo 10^9 + 7 instead.

  2. Hint 2

    Appending i means shifting the accumulator left by the bit width of i, then adding i.

  3. Hint 3

    The width only grows when i is a power of two, which i & (i - 1) == 0 detects.

How to solve Concatenation of Consecutive Binary Numbers

Keep a running value modulo 10⁹ + 7: appending i shifts the accumulator left by i's bit width and adds i; the width grows only at powers of two.

Approach

  1. For i from 1 to n: if i & (i - 1) == 0, increment width.
  2. answer = ((answer << width) + i) % MOD.

Why it works

Concatenating binary strings is multiplication by 2^width plus the new value, and modular reduction commutes with those operations.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Use 64-bit arithmetic for the intermediate shift in fixed-width languages.

Reference solution

Python

def concatenatedBinary(n: int) -> int:
    MOD = 1000000007
    answer = 0
    width = 0
    for i in range(1, n + 1):
        if i & (i - 1) == 0:
            width += 1
        answer = ((answer << width) + i) % MOD
    return answer

Java

public static int concatenatedBinary(int n) {
    final long MOD = 1000000007L;
    long answer = 0;
    int width = 0;
    for (int i = 1; i <= n; i++) {
        if ((i & (i - 1)) == 0) width++;
        answer = ((answer << width) + i) % MOD;
    }
    return (int) answer;
}

C++

int concatenatedBinary(int n) {
    const long long MOD = 1000000007LL;
    long long answer = 0;
    int width = 0;
    for (int i = 1; i <= n; i++) {
        if ((i & (i - 1)) == 0) width++;
        answer = ((answer << width) + i) % MOD;
    }
    return (int) answer;
}

JavaScript

var concatenatedBinary = function(n) {
    const MOD = 1000000007;
    let answer = 0;
    let width = 0;
    for (let i = 1; i <= n; i++) {
        if ((i & (i - 1)) === 0) width++;
        answer = (answer * Math.pow(2, width) + i) % MOD;
    }
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation