*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #1680 (*Medium*): Concatenation of Consecutive Binary Numbers

*Description:*

*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^9 + 7.

*Examples:*

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 <= 10^5

*Idea:*

There are less efficient solutions which involve converting numbers to strings, or calculating the binary length each time, but the most efficient solution is actually even more basic, since we know precisely when a binary number will increase its length by 1.

So we can just iterate through while using **len** to keep track of how much you need to multiply **ans** by in order to fit **i** into the new **ans**. Don't forget to mod by **1e9+7**.

*Javascript Code:*

```
var concatenatedBinary = function(n) {
let ans = 1, len = 0b100
for (let i = 2; i <= n; i++) {
if (i === len) len <<= 1
ans = (ans * len + i) % 1000000007
}
return ans
};
```

The same code but with decimal instead of binary for **len**:

```
var concatenatedBinary = function(n) {
let ans = 1, len = 4
for (let i = 2; i <= n; i++) {
if (i === len) len *= 2
ans = (ans * len + i) % 1000000007
}
return ans
};
```

## Top comments (0)