Bob and Queries

Bob has an array W of A integers. Initially, all the elements of the array are zero. Bob asks you to perform Q operations on this array.

There are three types of operations that can be performed

1 X -1: Update the value of A[X] to 2 * A[X] + 1.

2 X -1: Update the value A[X] to ⌊A[x]/2⌋ , where ⌊⌋ is Greatest Integer Function.

3 X Y: Take all the A[i] such that X <= i <= Y and convert them into their corresponding binary strings.
Now concatenate all the binary strings and find the total no. of ‘1’ in the resulting string.



Input Format

The first argument has the integer A.
The second argument is a 2d matrix B, of size Q x 3, representing the queries.

Output Format

Return an array of integers where ith index represents the answer of the ith type 3 query.

Constraints

1 <= A, Q <= 500000
1 <= X, Y <= N

For Example

Input 1:
    A = 5
    B = [   [1, 1, -1]
            [1, 2, -1]
            [1, 3, -1]   
            [3, 1, 3] 
            [3, 2, 4]   ]
Output 1:
    [3, 2]
Explanation 1:
    => [0, 0, 0, 0, 0]
    => [1, 0, 0, 0, 0]
    => [1, 1, 0, 0, 0]
    => [1, 1, 1, 0, 0]
    => Concatenation of Binary String between index 1 and 3 : 111
       Output : 3
    => Concatenation of Binary String between index 2 and 4 : 110
       Output : 2
       
 Input 2:
    A = 5
    B = [   [1, 1, -1]
            [1, 2, -1]
            [3, 1, 3]
            [2, 1, -1]
            [3, 1, 3]   ]
Output 2:
    [2, 1]
Explanation 2:
    => [0, 0, 0, 0, 0]
    => [1, 0, 0, 0, 0]
    => [1, 1, 0, 0, 0]
    => Concatenation of Binary String between index 1 and 3 : 110
       Output : 2
    => [0, 1, 0, 0, 0]
    => Concatenation of Binary String between index 2 and 4 : 010
       Output : 1
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Bob and Queries on Interview Code Editor
Sign Up
to access hints and editorial solutions for Bob and Queries

Discussion


Loading...
Click here to start solving coding interview questions