Concatenation of Consecutive Binary Numbers solution and explanation
Google
9 more videos on this problem
Concatenation of Consecutive Binary Numbers | Leetcode #1680Techdose · 15:29 · 8K views
Concatenation of Consecutive Binary Numbers | Two Approaches | Dry Run | Leetcode 1680 | MIKcodestorywithMIK · 13:16 · 8K views
Concatenation of Consecutive Binary Numbers | LeetCode 1680 | Modular Arithmetic & Bit ShiftingSanyam IIT Guwahati · 12:06 · 460 views
Leetcode - Concatenation of Consecutive Binary Numbers (Python)Timothy H Chang · 4:39 · 440 views
Daily Leetcode #2160: Feb 28, 2026 - 1680. Concatenation of Consecutive Binary NumbersProgramming Live with Larry · 10:08 · 402 views
1680. Concatenation of Consecutive Binary Numbers (Leetcode Medium)Programming Live with Larry · 16:53 · 347 views
1680. Concatenation of Consecutive Binary Numbers | Leetcode Daily - PythonLeetcode Daily · 8:00 · 331 views
Daily Leetcode #906: Sep 23, 2022 - 1680. Concatenation of Consecutive Binary NumbersProgramming Live with Larry · 9:09 · 282 views
Leetcode 1680. Concatenation of Consecutive Binary Numbers - Weekly Contest 218Friendly Neighborhood Coder · 4:36 · 251 views
Daily Leetcode #302: Jan 27, 2021 - 1680. Concatenation of Consecutive Binary NumbersProgramming Live with Larry · 19:40 · 175 views
The 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 109 + 7.
Example 1:
Input: n = 1 Output: 1 Explanation: "1" in binary corresponds to the decimal value 1.
Example 2:
Input: n = 3 Output: 27 Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11". After concatenating them, we have "11011", which corresponds to the decimal value 27.
Example 3:
Input: n = 12 Output: 505379714 Explanation: The concatenation results in "1101110010111011110001001101010111100". The decimal value of that is 118505380540. After modulo 109 + 7, the result is 505379714.
Constraints:
1 <= n <= 105
Approach overview
Problem Overview: Given an integer n, build a binary string by concatenating the binary representations of numbers from 1 to n in order. Convert the resulting binary value to decimal and return it modulo 1e9 + 7. Directly forming the full binary string becomes expensive as n grows, so the goal is to append bits efficiently while keeping the number within modulo limits.
Approach 1: Binary String Accumulation (O(n log n) time, O(n log n) space)
This approach simulates the process literally. Iterate from 1 to n, convert each number to its binary form using built-in conversion, and append it to a growing string. After building the final binary string, convert it to a decimal value and apply modulo 1e9 + 7. The logic is easy to reason about and mirrors the problem statement exactly.
The drawback is memory and runtime overhead. The resulting binary string grows to roughly O(n log n) bits because each number contributes up to log2(n) bits. String concatenation and large integer parsing also slow things down. This approach works for small inputs but struggles with large n. It mainly helps you understand the mechanics of binary concatenation before optimizing.
Approach 2: Bit Manipulation (O(n) time, O(1) space)
The optimal solution avoids building a string entirely. Instead, treat the result as a number and append bits using left shifts. When you append the binary representation of a number i, shift the current result left by the number of bits in i, then add i. In code this looks like result = ((result << bits) | i) % MOD.
The key detail is tracking how many bits i contains. Every time i reaches a power of two (1, 2, 4, 8, ...), the bit length increases by one. Detect this with the condition (i & (i - 1)) == 0. This technique comes from bit manipulation and lets you update the bit count in constant time.
This solution processes each number once and performs only simple bit shifts and modulo operations. The runtime is O(n) and space is O(1). The logic also highlights the mathematical structure of the problem, connecting binary length growth with powers of two, a concept often used in math and simulation style problems.
Recommended for interviews: The bit manipulation approach is the expected answer. Interviewers want to see that you avoid constructing the binary string and instead append bits using shifts. Mentioning the brute-force string approach first shows clear reasoning about the problem, while the optimized shift-based method demonstrates strong understanding of binary representation and time complexity.
Approach 1: Bit Manipulation
This method leverages bit manipulation to efficiently construct the resulting number without physically concatenating binary strings. As each integer from 1 to n is processed, its binary representation is appended using bitwise operations, which helps avoid the overhead of string manipulation.
def concatenatedBinary(n):
MOD = 10**9 + 7
result = 0
bit_length = 0
for i in range(1, n + 1):
# When i is a power of 2, increment the length of binary digits
if i & (i - 1) == 0:
bit_length += 1
result = ((result << bit_length) | i) % MOD
return resultclass Solution {
public int concatenatedBinary(int n) {
int MOD = 1000000007;
long result = 0;
int bitLength = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) bitLength++;
result = ((result << bitLength) | i) % MOD;
}
return (int) result;
}
}#include <iostream>
using namespace std;
class Solution {
public:
int concatenatedBinary(int n) {
const int MOD = 1000000007;
long result = 0;
int bitLength = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) bitLength++;
result = ((result << bitLength) | i) % MOD;
}
return (int)result;
}
};const concatenatedBinary = function(n) {
const MOD = 1000000007;
let result = 0;
let bitLength = 0;
for (let i = 1; i <= n; i++) {
if ((i & (i - 1)) === 0) bitLength++;
result = ((result << bitLength) | i) % MOD;
}
return result;
};
console.log(concatenatedBinary(12));#include <stdio.h>
#define MOD 1000000007
int concatenatedBinary(int n) {
long result = 0;
int bitLength = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) bitLength++;
result = ((result << bitLength) | i) % MOD;
}
return (int)result;
}
int main() {
int n = 12;
printf("Output: %d\n", concatenatedBinary(n));
return 0;
}using System;
public class Solution {
public int ConcatenatedBinary(int n) {
const int MOD = 1000000007;
long result = 0;
int bitLength = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) bitLength++;
result = ((result << bitLength) | i) % MOD;
}
return (int)result;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.ConcatenatedBinary(12));
}
}In this implementation, a loop iterates through each number from 1 to n. When the loop reaches a new power of 2, the binary length of numbers increases by one. Using left shift operations, we append the current number, then apply the modulo operation to keep the result manageable.
Time Complexity: O(n), because we process each number from 1 to n.
Space Complexity: O(1), as we use a fixed amount of additional space.
Approach 2: Binary String Accumulation
This naive strategy involves directly constructing the final binary string representation step by step. After forming the complete string, it converts it to an integer and performs modulo operation. This approach might be less efficient for large n due to string operations being costly.
def concatenatedBinary(n):
MOD = 10**9 + 7
binary_string = ''
for i in range(1, n + 1):
binary_string += bin(i)[2:]
return int(binary_string, 2) % MODimport java.math.BigInteger;
class Solution {
public int concatenatedBinary(int n) {
int MOD = 1000000007;
StringBuilder binaryString = new StringBuilder();
for (int i = 1; i <= n; i++) {
binaryString.append(Integer.toBinaryString(i));
}
return new BigInteger(binaryString.toString(), 2).mod(BigInteger.valueOf(MOD)).intValue();
}
}#include <iostream>
#include <bitset>
#include <string>
class Solution {
public:
int concatenatedBinary(int n) {
const int MOD = 1000000007;
std::string binaryString = "";
for (int i = 1; i <= n; i++) {
binaryString += std::bitset<32>(i).to_string().substr(32 - bit_length(i));
}
long result = 0;
for (char c : binaryString) {
result = (result * 2 + c - '0') % MOD;
}
return (int)result;
}
private:
int bit_length(int number) {
int length = 0;
while (number > 0) {
number >>= 1;
length++;
}
return length;
}
};const concatenatedBinary = function(n) {
const MOD = 1000000007;
let binaryString = '';
for (let i = 1; i <= n; i++) {
binaryString += i.toString(2);
}
let result = 0;
for (let ch of binaryString) {
result = (result * 2 + parseInt(ch)) % MOD;
}
return result;
};
console.log(concatenatedBinary(12));#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int concatenatedBinary(int n) {
const int MOD = 1000000007;
char binaryString[1000000] = "";
char buffer[33];
for (int i = 1; i <= n; i++) {
snprintf(buffer, 33, "%s", itoa(i, buffer, 2));
strcat(binaryString, buffer);
}
long long result = 0;
for (int j = 0; binaryString[j] != '\0'; j++) {
result = (result * 2 + binaryString[j] - '0') % MOD;
}
return (int)result;
}
int main() {
int n = 12;
printf("Output: %d\n", concatenatedBinary(n));
return 0;
}using System;
public class Solution {
public int ConcatenatedBinary(int n) {
const int MOD = 1000000007;
System.Text.StringBuilder binaryString = new System.Text.StringBuilder();
for (int i = 1; i <= n; i++) {
binaryString.Append(Convert.ToString(i, 2));
}
long result = 0;
foreach (char ch in binaryString.ToString()) {
result = (result * 2 + (ch - '0')) % MOD;
}
return (int)result;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.ConcatenatedBinary(12));
}
}This approach builds a complete string of concatenated binary representations of numbers from 1 to n, converts it to integer, and applies modulo.
Time Complexity: O(n * log n), as string operations for binary conversions dominate computation time.
Space Complexity: O(n * log n), due to the storage of the growing binary string.
Approach 3: Bit Manipulation
By observing the pattern of number concatenation, we can find that when concatenating to the i-th number, the result ans formed by concatenating the previous i-1 numbers is actually shifted to the left by a certain number of bits, and then i is added. The number of bits shifted is the number of binary digits in i.
The time complexity is O(n), where n is the given integer. The space complexity is O(1).
function concatenatedBinary(n: number): number {
const mod = 1_000_000_007;
let ans = 0;
for (let i = 1; i <= n; i++) {
ans = (((ans * (1 << (32 - Math.clz32(i)))) % mod) + i) % mod;
}
return ans;
}func concatenatedBinary(n int) (ans int) {
const mod = 1e9 + 7
for i := 1; i <= n; i++ {
ans = (ans<<bits.Len(uint(i)) | i) % mod
}
return
}impl Solution {
pub fn concatenated_binary(n: i32) -> i32 {
let mod_: i64 = 1_000_000_007;
let mut ans: i64 = 0;
for i in 1..=n as i64 {
let bit_length: u32 = 64 - i.leading_zeros() as u32;
ans = ((ans << bit_length) | i) % mod_;
}
ans as i32
}
}Approach 4: Bit Manipulation (Optimization)
In Solution 1, we need to calculate the number of binary digits of i each time, which adds some extra computation. We can use a variable shift to record the current number of bits to shift. When i is a power of 2, shift needs to be incremented by 1.
The time complexity is O(n), where n is the given integer. The space complexity is O(1).
function concatenatedBinary(n: number): number {
const mod = 1_000_000_007;
let ans = 0;
let shift = 0;
for (let i = 1; i <= n; i++) {
if ((i & (i - 1)) === 0) {
shift++;
}
ans = (((ans * (1 << shift)) % mod) + i) % mod;
}
return ans;
}func concatenatedBinary(n int) (ans int) {
const mod = 1e9 + 7
shift := 0
for i := 1; i <= n; i++ {
if i&(i-1) == 0 {
shift++
}
ans = (ans<<shift | i) % mod
}
return
}impl Solution {
pub fn concatenated_binary(n: i32) -> i32 {
let mod_: i64 = 1_000_000_007;
let mut ans: i64 = 0;
let mut shift: u32 = 0;
for i in 1..=n as i64 {
if (i & (i - 1)) == 0 {
shift += 1;
}
ans = ((ans << shift) | i) % mod_;
}
ans as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bit Manipulation | Time Complexity: O(n), because we process each number from 1 to n. Space Complexity: O(1), as we use a fixed amount of additional space. |
| Binary String Accumulation | Time Complexity: O(n * log n), as string operations for binary conversions dominate computation time. Space Complexity: O(n * log n), due to the storage of the growing binary string. |
| Bit Manipulation | – |
| Bit Manipulation (Optimization) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary String Accumulation | O(n log n) | O(n log n) | Conceptual or brute-force implementation when constraints are small and clarity is preferred. |
| Bit Manipulation with Left Shift | O(n) | O(1) | Optimal solution for large n. Avoids building strings and appends binary digits using shifts. |
Frequently asked questions
Is Concatenation of Consecutive Binary Numbers easy or hard?
The problem is rated Medium because the straightforward idea of concatenating binaries leads to inefficient solutions. The challenge is recognizing that binary concatenation can be simulated with bit shifts and detecting when the bit length increases.
Concatenation of Consecutive Binary Numbers Python/Java solution
Python and Java implementations both follow the same logic: iterate from 1 to n, detect when the bit length increases (power of two), left shift the current result, add the number, and take modulo 1e9+7. The algorithm remains O(n) time and O(1) space across languages.
How to solve Concatenation of Consecutive Binary Numbers in O(n)?
Iterate from 1 to n while maintaining a running result. When the current number is a power of two, increase the bit length counter. Left shift the result by this bit length, OR it with the current number, and apply modulo 1e9+7. This simulates binary concatenation using arithmetic instead of strings.
What is the best approach for Concatenation of Consecutive Binary Numbers?
The best approach uses bit manipulation with left shifts. Instead of building a binary string, maintain a running integer result. For each number i from 1 to n, shift the current result left by the number of bits in i and OR it with i. This runs in O(n) time and O(1) space.
Is Concatenation of Consecutive Binary Numbers asked at Google/Amazon/Meta?
Problems involving bit manipulation and binary representation frequently appear in interviews at companies like Google, Amazon, and Meta. This specific problem tests understanding of binary length growth, bit shifts, and modular arithmetic, which are common interview topics.
What data structure is used in Concatenation of Consecutive Binary Numbers?
The optimal solution does not rely on complex data structures. It uses integer variables and bit manipulation operations such as left shift and bitwise OR. The brute-force version may use a string builder to accumulate binary digits.
What is the time complexity of Concatenation of Consecutive Binary Numbers?
The optimal bit manipulation solution runs in O(n) time because each number from 1 to n is processed once with constant-time bit operations. Space complexity is O(1). A naive approach that concatenates binary strings takes O(n log n) time and space due to string growth.