Question

Triology | CodeNation | Coding | OA | SDE | Set-6

Answer 1

The following problems are from the Codenation coding round held on 12th June.. 

I was not able to solve these problems, and it would be very helpful if you guys could give a rough idea of the solution....

 

Q1. You have two integer arrays X  and Y of size n. 

Initially, all the elements in both these arrays are 0. 

You have to process q queries, each query can be of three types:

• 1 l r : Flip all 0 to 1 and all 1 to 0 in the range [l,...,r] in the array X

• 2 p : Y[i]=Y[i]+p⋅X[i] for all ∈[1,...,]

• 3 j : Find Y[j]

Input: n, q, and all the queries, 

Output: For every query of type 3, print Y[j]

Constraints: 1≤n≤100000, 1≤q≤500000, 1≤l≤r≤n, 1≤p≤100000000, 1≤j≤n

Q2. Given a number , find the number of actual greater pairs. A pair (,) is an actual greater pair if:

• 0≤<≤
• sum of digits of < sum of digits of 

Since  can be very large, you have to input it as a string. Return the number of actual greater pairs modulo 19+7

Input: , Output: number of actual greater pairs modulo 1e9+7

Constraints: 1<=n<= 10^(100)