Solution: Concatenation of Consecutive Binary Numbers

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
};