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
Hint 1
Building the string explicitly overflows fast — keep a running value modulo
10^9 + 7instead.Hint 2
Appending
imeans shifting the accumulator left by the bit width ofi, then addingi.Hint 3
The width only grows when
iis a power of two, whichi & (i - 1) == 0detects.
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
- For
ifrom 1 ton: ifi & (i - 1) == 0, incrementwidth. 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 answerJava
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