1680. Concatenation of Consecutive Binary Numbers

Concatenation of Consecutive Binary Numbers

Problem 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 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

Idea:

There are less efficient solutions that 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.

Let`s Code IT!

The best result for the code below is 148ms / 39.8MB (95% / 84%).

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

Complexity 

Time Complexity
We are using a single loop hence, its complexity is O(n)


Space Complexity
We are using constant space to store ans, and len so O(1)

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1680. Concatenation of Consecutive Binary Numbers

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!