Concatenation of Consecutive Binary Numbers

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in company
Grofers

Problem statement

Tony Stark has come to the Ninja with a proposal to join his team of Avengers. Ninja is very excited to join the team, but Tony put him in trouble by asking him to decode a secret code corresponding to an integer, which is the criteria for joining the team.

Tony gave him a number ‘N’ for which the secret code will be the decimal value of the binary string formed by concatenating the binary representations of 1 to ‘N’ in order. Ninja desperately wants to join the team, so he needs your help to find the secret code.

For example:

Given N = 3. The binary representation of 1, 2, and 3 are 1, 10, and 11, respectively. So, the string formed by concatenating the binary representation of 1, 2, and 3 is “11011”, whose decimal value is 27. Therefore, the secret code corresponding to N = 3 is 27.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first and only line of each test case contains an integer ‘N’ to be decoded.

Output Format:

For each test case, print a single line containing a single integer denoting the decimal value of the binary string formed by concatenating the binary representations of 1 to ‘N’ in order. Since the decimal value can be very large, print the answer after modulo 1000000007.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 3000

Where ‘T’ is the number of test cases and ‘N’ is the integer to be decoded.

Time limit: 1 sec.

Sample Input 1:

2
5
2

Sample Output 1:

1765
6

Explanation of Sample Output 1:

Test Case 1 :  
Given N = 5.
The binary representation of 1 is 1.
The binary representation of 2 is 10.
The binary representation of 3 is 11.
The binary representation of 4 is 100.
The binary representation of 5 is 101.
After concatenating, string = “11011100101”, whose decimal value is 1765.
Therefore, the secret code corresponding to N = 5 is 1765, which is printed as output.

Test Case 2 :
Given N = 2.
The binary representation of 1 is 1.
The binary representation of 2 is 10.
After concatenating, string = “110” whose decimal value is 6.
Therefore, the secret code corresponding to N = 2 is 6, which is printed as output.

Sample Input 2:

2
1
40

Sample Output 2:

1
603205042
Hint

Use brute force approach to generate a binary string as per the given problem statement.

Approaches (3)
Brute Force

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’.
Time Complexity

O(N * log(N))), where ‘N’ is the integer to be decoded.

 

The ‘createBinaryString’ function finds the binary representation of every integer in the range [1, N]. So, the time taken by ‘createStringFunction’ will be:

log(1) + log(2) + log(3) + . . . + log(N) = log(1 * 2 * 3 * . . . * N) = log(N!) = O(N * log(N)).

To find the decimal value corresponding to ‘BINARYREP’, the loop makes BINARYREP.length() iterations within which every iteration performs O(1) operation. Since the length of BINARYREP is O(N * log(N)). The time complexity of finding the decimal value corresponding to ‘BINARYREP’ is also O(N * log(N))).

Therefore, overall time complexity = O(N * log(N))) + O(N * log(N))) = O(N * log(N))).

Space Complexity

O(N * log(N)), where ‘N’ is the integer to be decoded.

 

Since O(N * log(N)) space is required to store the binary representation of every integer in the range [1, N].

Code Solution
(100% EXP penalty)
Concatenation of Consecutive Binary Numbers
Full screen
Console