Algorithm to Compute the Concatenation of Consecutive Binary Numbers

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.

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 10^9 + 7, the result is 505379714.
Constraints:
1 <= n <= 10^5

Concatenation of Consecutive Binary Numbers

Given a binary string, we know how to convert it to decimals. The algorithm to solve this is actually quite similar. We shift the current result to the left to accomodate the new binary number.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int concatenatedBinary(int n) {
        constexpr int M = 1e9+7;
        int64_t ans = 0;
        for (int i = 1; i <= n; ++ i) {
            int curLen = ceil(log2(i + 1));
            ans = ((ans << curLen) + i) % M;
        }
        return ans;
    }
};

class Solution {
public:
    int concatenatedBinary(int n) {
        constexpr int M = 1e9+7;
        int64_t ans = 0;
        for (int i = 1; i <= n; ++ i) {
            int curLen = ceil(log2(i + 1));
            ans = ((ans << curLen) + i) % M;
        }
        return ans;
    }
};

To compute the length of a decimal number in its binary string format, we can use the log2 function – alternatively, we can use the compiler intrinsic (GCC provides) __builtin_clz to compute the number of leading zeros.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int concatenatedBinary(int n) {
        constexpr int M = 1e9+7;
        int64_t ans = 0;
        for (int i = 1; i <= n; ++ i) {
            int curLen = 32 - __builtin_clz(i);
            ans = ((ans << curLen) + i) % M;
        }
        return ans;
    }
};

class Solution {
public:
    int concatenatedBinary(int n) {
        constexpr int M = 1e9+7;
        int64_t ans = 0;
        for (int i = 1; i <= n; ++ i) {
            int curLen = 32 - __builtin_clz(i);
            ans = ((ans << curLen) + i) % M;
        }
        return ans;
    }
};

See the Python version for more algorithms on this solution: Teaching Kids Programming – Concatenation of Consecutive Binary Numbers

–EOF (The Ultimate Computing & Technology Blog) —