Teaching Kids Programming – Concatenation of Consecutive Binary Numbers

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 via Bruteforce Algorithm

We can do what we are told to do. The bruteforce algorithm is most straightforward and intuitive solution. We can use the bin function to convert the integer to binary, and then concatenate them, and use int to convert the string into decimal (and we need to specify the base 2 in the second parameter).

1
2
3
4
5
6

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        arr = [bin(i)[2:] for i in range(1, n + 1)]
        val = "".join(arr)
        MOD = 10**9+7
        return int(val, 2) % MOD

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        arr = [bin(i)[2:] for i in range(1, n + 1)]
        val = "".join(arr)
        MOD = 10**9+7
        return int(val, 2) % MOD

Simply one-liner:

1
2
3

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        return int("".join([bin(i)[2:] for i in range(1, n + 1)]), 2) % (10**9+7)

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        return int("".join([bin(i)[2:] for i in range(1, n + 1)]), 2) % (10**9+7)

The time complexity is O(NLogN) as we need to iterate the N integers, and for each number, we call bin which is O(LogN) to convert to binary string. And the space is O(NLogN) as we need an array.

Concatenation of Consecutive Binary Numbers via Bit Shifting (MATH)

Suppose next number comes in, we know the binary string and we know the length is x, what happens to the current value? It shifts x position to the left, thus value multiply by 2^x. It is a process of converting a binary to decimal.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        ans = 0
        M = 10**9+7
        for i in range(1, n + 1):
            curL = len(bin(i)) - 2
            ans <<= curL
            ans += i
            ans %= M
        return ans

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        ans = 0
        M = 10**9+7
        for i in range(1, n + 1):
            curL = len(bin(i)) - 2
            ans <<= curL
            ans += i
            ans %= M
        return ans

The time complexity is O(NLogN) like the first solution. The space complexity is improved to O(1) constant.

The bin function at each iteration is O(LogN) which we want to avoid. We don’t actually require the binary string, but only need to know the length here. The number of digits increments by one when number is a power of two such as 2, 4, 8… their binary representation is 1000…

So, we can just keep the length in a variable, and increment/update it when the number is power of two:

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

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        ans = 0
        M = 10**9+7
        curL = 0
        for i in range(1, n + 1):
            if i & (i - 1) == 0:
                curL += 1
            ans <<= curL
            ans += i
            ans %= M
        return ans

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        ans = 0
        M = 10**9+7
        curL = 0
        for i in range(1, n + 1):
            if i & (i - 1) == 0:
                curL += 1
            ans <<= curL
            ans += i
            ans %= M
        return ans

There are a few ways to check if an integer is power of two, but the above is the fastest which is based on bit checking on the format of 1 followed by zeros. Here are a few others:

• Multiple by two from 1, until we hit target (true) or exceed it (false)
• Divide by two if it is even until we hit one (true) or false otherwise
• check math.log(x, 2).is_integer() is a whole integer
• get the integer part e.g. x=int(math.log(i,2)); and then reverse check 2**x==i

The time complexity is O(N) as we no longer require bin function in each iteration. The space complexity is O(1).

See also: Algorithm to Compute the Concatenation of Consecutive Binary Numbers

–EOF (The Ultimate Computing & Technology Blog) —