Concatenation of Consecutive Binary Numbers

The idea is to use the brute force approach.

For every integer in the range [1, N], we will find out its binary representation and concatenate them to create a string. Then, we will traverse the string and find its decimal value.

For a binary string, “11011100”, the decimal value is calculated as: (1 * 2 ^ 7) + (1 * 2 ^ 6) + (0 * 2 ^ 5) + (1 * 2 ^ 4) + (1 * 2 ^ 3) + (1 * 2 ^ 2) + (0 * 2 ^ 1) + (0 * 2 ^ 0) = 220.

Algorithm:

• Call ‘createBinaryString’ function with parameter ‘N’ to find the binary string formed by concatenating the binary representations of 1 to ‘N’ and store the returned value in a string variable, ‘BINARYREP’.
• Declare two integer variables, ‘RESULT’ and ‘FACTOR’. Initialize the ‘RESULT’ with 0 and ‘FACTOR’ with 1. The ‘RESULT’ will store the final decimal value of the ‘BINARYREP’ string, and ‘FACTOR’ will hold the value to be multiplied with the corresponding bit of ‘BINARYREP’ in every iteration.
• Run a loop for i = BINARYREP.length() - 1 till i = 0.
  • If BINARYREP[ i ] == ‘1’, that shows that the current bit is set. Therefore,
    • Add ‘FACTOR’ to the ‘RESULT’.
    • Take modulo 1000000007 of ‘RESULT’.
  • Multiply ‘FACTOR’ by 2 under modulo 1000000007.
• In the end, return ‘RESULT’.

Description of ‘createBinaryString’ function

This function will take only one parameter:

• N: An integer variable to find the binary string formed by concatenating the binary representations of 1 to ‘N’.

void createBinaryString(N):

• Declare a string variable, ‘STR’, that will store the binary string formed by concatenating the binary representations of 1 to ‘N’.
• Run a loop for i = 1 to N.
• Declare an integer variable, ‘DECIMALNUM’ and assign ‘i’ to it.
• Declare a string variable, ‘BINARYNUM’, that will store the binary representation of ‘DECIMALNUM’.
• Run a loop while DECIMALNUM > 0.
  • Declare a character variable, ‘BIT’ and assign (DECIMALNUM % 2 + ‘0’) to it.
  • Push the ‘BIT’ in ‘BINARYNUM’.
  • Divide the ‘DECIMALNUM’ by 2.
• Append the reverse of ‘BINARYNUM’ in ‘STR’.
• Return ‘STR’.

We do not need to create a whole concatenated string for all integers from 1 to ‘N’. If we look more closely, then the next integer’s binary representation causes a left shift to the binary representation of the previous integer by the length of the binary representation of the next integer.

For example: Suppose we want to decode the value for N = 4.

Then,

For N = 1, Binary Representation = 1 => String = “1”.

For N = 2, Binary Representation = 10 => String =  “1” + “10” = “110”.

We can see that the previous string “1” has been left-shifted by 2, i.e., the length of “10”.

For N = 3, Binary Representation = 11 => String = “110”  + “11” = “11011”.

Again, the previous string “110” has been left-shifted by 2, i.e., the length of “11”.

For N = 4, Binary Representation = 100 => String = “11011” + “100” = “11011100”.

Here, the previous string “11011” has been left-shifted by 3, i.e., the length of “100”.

With this observation, we can easily find the final decimal representation.

N String Result

1 “1” 1

2 “1 10” 1 << 2 + 2 = 6

3 “110 11” 6 << 2 + 3 = 27

4 “11011 100” 27 << 3 + 4 = 220

Therefore, the generalised formula will be “Result = Previous Result << Length of Current Binary Representation + Current Integer”.

Note: Any decimal number, ‘N’ has ‘log2(N) + 1’ digits in its binary representation.

Algorithm:

• Declare two ‘LONG LONG INT’ variables, ‘RESULT’ and ‘LENGTH’. Initialize the ‘RESULT’ with 0. The ‘RESULT’ will store the final decimal value, and ‘LENGTH’ will store the length of the binary representation of an integer.
• Run a loop for i = 1 to N.
  • Assign ‘log2(i) + 1’ in ‘LENGTH’.
  • Update ‘RESULT’ by ‘RESULT << LENGTH’.
  • Add ‘i’ to the ‘RESULT’.
  • Take modulo 1000000007 of ‘RESULT’.
• In the end, return ‘RESULT’.

We can use bitwise operators to decrease the runtime of the logic mentioned in Approach 2.

Optimization 1:

Instead of using the ‘log’ operator to count the number of digits, we will use the fact that the length only increments when the integer is a power of 2. So, we will initialize ‘LENGTH’ with 0 and increment it only when for any integer, ‘i’ : (i & (i - 1)) == 0, i.e. ‘i’ has single bit 1.

Optimization 2:

Instead of using the ‘+’ operator to append the current integer, we can use bitwise OR ‘|’.

Algorithm:

• Declare two ‘LONG LONG INT’ variables, ‘RESULT’ and ‘LENGTH’. Initialize the ‘RESULT’ as well as ‘LENGTH’ with 0. The ‘RESULT’ will store the final decimal value, and ‘LENGTH’ will store the length of the binary representation of an integer.
• Run a loop for i = 1 to N.
  • If (i & (i - 1)) == 0 that shows that ‘i’ has single bit 1. So,
    • Increment the ‘LENGTH’ by 1.
  • Update ‘RESULT’ by ‘RESULT << LENGTH’.
  • Take bitwise OR ‘|’ of ‘i’ with the ‘RESULT’.
  • Take modulo 1000000007 of ‘RESULT’.
• In the end, return ‘RESULT’.