14 months ago

PoGo 2.4k

Mumbai

Step Sequence :

What Is the sum of all numbers in array A that meet certain conditions?

Here's how it works: You have an array A containing N numbers, and you also have Q queries. Each query asks for the sum of all numbers that are available in array A and are part of a K-step
sequence and have their indexes in the range L to R. A K-step sequence for the given array can be defined as A[i], A[i+ k], A[i+ 2k].. where k is a fixed step size. Your task is to print Q lines, where each line contains a
single integer representing the answer to the corresponding query.

Function description

Complete the solved function. This function takes the following 4
parameters and returns an array of answers:

• N. Represents the size of array A
•  A: Represents the elements of the array

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code

•The first line contains 7. which represents the number of test
cases.

• For each test case:

• The first line contains a single integer N denoting the number of elements in array A
• The next line of each test case contains N space. separated integers denoting the elements of array A
• The next line contains a single integer Q denoting the number of queries.
• Each of the next Q lines describes a single query.

Output format

Print Q lines in which the / line contains a single integer denoting the answer to the / query.

Constraints

• 1 ≤ T ≤5
• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10°
• 1 < A[i], K < 10⁹
• 1≤ L ≤ R ≤N

Sample Input            Sample Output

1                             9
5                             2
1 5 9 2 3                     20
3
2 4 2
1 4 3
1 5 1

Explanation

The first line contains the number of test cases. T=1
Given
• N= 5
• A = [1 5 9, 2. 3)
• Q=3
• Queries = (12, 4, 2]. [1, 4. 3). [1 5, 1]

Approach

• L = 2. R = 4. K = 2The 2 step sequence consists of elements 1, 9 and 3 Out of these, only 9 have an index in the range of 2 to 4 Hence answer is 9
• L= 1 R= 5 K = 1The 1-step sequence consists of elements 1, 5, 9 , 2 and 3 Out of these all have their indexes in the range of 1 to 5 Hence answer is 1 ÷ 5 + 9 * 2 ÷ 3 = 20
•  L= 1 R = 4 K = 3 The 3 step sequence consists of elements fand 2 Out of these both have their indexes in the range of to 4 Hence answer is 1 ÷ 2 = 3

Sample Input 

5

100000

767323822  772159313 43787796

100000

1 100000 2

1 100000 3

1 100000 4

1 100000 5

1 100000 6

1 100000 7


Sample output 

23453022713349

15723121667990

11734056901599

9408021944749

7860799419378

6706480277411

5808075472155

Sample Input

5

100000

767391050  902060309 48602731

100000

1 100000 2
1 100000 3
1 100000 4
1 100000 5
1 100000 6
1 100000 7



Sample Output

23509388078932
15630376754699
11707778135717
9378197087731
7794048448648
6735532161705
588927669906
5222563249646
4711992812329
47053382551851

Possible decryptions

You are working in the Cyber Security team of your company. You are working on a decryption algorithm that converts an integer into the number of set bits present in the integer. You have to
determine the possible number of decryptions with certain conditions such as: A number can be called a possible decryption if it can be changed Into 1 by passing it Into the decryption algorithm continuously K times
with the result coming as in the Kth step. For example, in step 12, I.e (1100) can be converted Into 2 because it has 2 set bits.

For the experiment, you are given a binary string representing a number N and an integer K.

Find the number of possible decryptions not greater than N modulo 10⁹ + 7.

Function description

Complete the function Decryptions. This function takes the following 2 parameters and returns the required answer;

• N: Represents the binary string
• K: Represents the number of steps in which a number should become 1 to be a possible decryption

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code,

The first line contains the binary string N.
The second line contains integer K.
Note: N is given in its binary representation without
any leading zeros.

Output format

Print the number of possible decryptions not greater than N modulo 10⁹ + 7.

Constraints

1 ≤ |N| ≤ 437

0 ≤  K ≤ 700

Sample input            Sample output
     110                     3
      2