# Concatenation of Consecutive Binary Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers)
Canonical: https://scaleengineer.com/dsa/problems/concatenation-of-consecutive-binary-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## 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`

# Approaches
## Brute Force with String Concatenation
This approach directly simulates the process described in the problem. It iterates from 1 to `n`, converts each number to its binary string representation, and concatenates these strings. Finally, it converts the resulting long binary string into a decimal number and applies the modulo operation.
**Time:** O(N log N). The total length of the string is `S = O(N log N)`. Building this string takes `O(S)`. Converting the string of length `S` to a `BigInteger` and performing the modulo operation also takes time proportional to `S` or more. · **Space:** O(N log N), where N is the input `n`. The total length of the concatenated binary string is the sum of the bit lengths of numbers from 1 to N, which is approximately `N log N`.
**Pros:** Simple and easy to understand.; Directly translates the problem statement into code.
**Cons:** Highly inefficient for large `n`.; High memory usage due to the long intermediate string, which can lead to `OutOfMemoryError`.; `BigInteger` operations are computationally expensive.; Likely to result in a "Time Limit Exceeded" error on competitive programming platforms.
### Explanation
The core idea is to build the complete binary string first. We use a `StringBuilder` for efficient string concatenation. A loop runs from `i = 1` to `n`. In each step, `Integer.toBinaryString(i)` is called to get the binary form of `i`, which is then appended to the `StringBuilder`. After the loop, the concatenated binary string can be extremely long, exceeding the capacity of standard primitive types like `long`. Therefore, we must use `java.math.BigInteger` to handle the conversion from this binary string to its decimal equivalent. Once we have the `BigInteger` representation, we can use its `mod()` method to find the result modulo `10^9 + 7`. Finally, we convert the result back to an `int`.

```java
import java.math.BigInteger;

class Solution {
    public int concatenatedBinary(int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(Integer.toBinaryString(i));
        }
        BigInteger mod = new BigInteger("1000000007");
        BigInteger decimalValue = new BigInteger(sb.toString(), 2);
        return decimalValue.mod(mod).intValue();
    }
}
```
### Algorithm
- Initialize a `StringBuilder` `sb`.
- Iterate with a variable `i` from 1 to `n`.
- For each `i`, convert it to a binary string using `Integer.toBinaryString(i)`.
- Append the binary string to `sb`.
- After the loop, create a `BigInteger` from the string in `sb`, specifying base 2.
- Calculate the `BigInteger` modulo `10^9 + 7`.
- Return the integer value of the result.

## Iterative Mathematical Approach
This approach avoids building a large string by calculating the decimal value iteratively. For each number `i` from 1 to `n`, we update the running total by shifting it left by the number of bits in `i` and then adding `i`. This avoids the high memory usage of the brute-force method.
**Time:** O(N log N). The main loop runs `N` times. Inside the loop, calculating the number of bits for `i` by converting it to a string takes `O(log i)` time. The total time is the sum of `log i` from `i=1` to `N`, which is `O(N log N)`. · **Space:** O(1). We only use a constant amount of extra space for variables. (Note: `Integer.toBinaryString` might use temporary space proportional to `log i`, but this is not accumulated).
**Pros:** Vastly improved space complexity compared to the brute-force approach.; Avoids `BigInteger`, which is slow.; Passes within the time limits for the given constraints.
**Cons:** The time complexity can still be improved.; The repeated calculation of bit length in each iteration is suboptimal.
### Explanation
The key insight is that concatenating the binary representation of `i` (which has `d` bits) to the current result is equivalent to a mathematical operation: `new_result = (current_result * 2^d) + i`. The term `current_result * 2^d` is simply `current_result` left-shifted by `d` bits (`current_result << d`). Since the result can become very large, we apply the modulo `10^9 + 7` at each step of the iteration to keep the numbers within the range of a `long`. The update rule becomes: `result = ((result << d) + i) % MOD`. In this version of the approach, we calculate the number of bits `d` for each `i` by converting `i` to a string and getting its length.

```java
class Solution {
    public int concatenatedBinary(int n) {
        long result = 0;
        final int MOD = 1_000_000_007;
        for (int i = 1; i <= n; i++) {
            // Calculate number of bits for i
            int numBits = Integer.toBinaryString(i).length();
            
            // Shift the current result left by numBits and add i
            result = ((result << numBits) % MOD + i) % MOD;
        }
        return (int) result;
    }
}
```
### Algorithm
- Initialize a `long` variable `result = 0` and `MOD = 10^9 + 7`.
- Iterate with `i` from 1 to `n`.
- For each `i`, calculate its bit length, `numBits`. For example, by using `Integer.toBinaryString(i).length()`.
- Update `result`: `result = ((result << numBits) + i) % MOD`.
- After the loop, cast the final `result` to `int` and return.

## Optimized Iterative Approach with Bit Manipulation
This is an optimization of the iterative approach. We observe that the number of bits we shift by only increases when the current number `i` is a power of two. We can leverage this fact to avoid recalculating the bit length in every iteration, leading to an `O(N)` solution.
**Time:** O(N). The loop runs `N` times, and all operations inside the loop (bitwise AND, comparison, increment, shift, add, modulo) take constant time. · **Space:** O(1). We only use a few variables, requiring constant extra space.
**Pros:** Optimal time complexity.; Optimal space complexity.; Very fast and efficient for the given constraints.
**Cons:** The logic, especially the power-of-two check, is more advanced than the more straightforward approaches.
### Explanation
This approach builds upon the iterative formula: `result = ((result << numBits) + i) % MOD`. The key optimization is in how we determine `numBits`. The number of bits in the binary representation of `i` increases by one only when `i` is a power of two (e.g., 1, 2, 4, 8, ...). We can maintain a counter for the current number of bits, `len`. We initialize `len = 0`. In our loop from `i = 1` to `n`, we first check if `i` is a power of two. A positive integer `i` is a power of two if and only if `(i & (i - 1)) == 0`. If `i` is a power of two, we increment `len`. Then, we use the current value of `len` to perform the shift and update the result: `result = ((result << len) + i) % MOD`. This avoids the `O(log i)` work of finding the bit length inside every iteration, reducing the work to a constant-time check.

```java
class Solution {
    public int concatenatedBinary(int n) {
        long result = 0;
        int len = 0; // The number of bits in the current number i
        final int MOD = 1_000_000_007;

        for (int i = 1; i <= n; i++) {
            // Check if i is a power of 2
            if ((i & (i - 1)) == 0) {
                len++;
            }
            
            // Shift the current result left by len and add i
            result = ((result << len) + i) % MOD;
        }
        return (int) result;
    }
}
```
### Algorithm
- Initialize `long result = 0`, `int len = 0`, and `MOD = 10^9 + 7`.
- Iterate with `i` from 1 to `n`.
- Inside the loop, check if `i` is a power of two using the bitwise trick `(i & (i - 1)) == 0`.
- If it is, increment `len`.
- Update the result using the current `len`: `result = ((result << len) + i) % MOD`.
- After the loop, cast `result` to `int` and return.

# Solutions
### Java

```java
class Solution {
public
  int concatenatedBinary(int n) {
    final int mod = (int)1 e9 + 7;
    long ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans = (ans << (32 - Integer.numberOfLeadingZeros(i)) | i) % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int concatenatedBinary(int n) {
    const int mod = 1e9 + 7;
    long ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans = (ans << (32 - __builtin_clz(i)) | i) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def concatenatedBinary(self, n: int) -> int: mod = 10 ** 9 + 7 ans = 0 for i in range(1, n + 1): ans = (ans << i . bit_length() | i) % mod return ans

```