Given an array $$$A$$$ of length $$$N$$$ with positive elements $$$a_1, a_2,...,a_N$$$ and two numbers $$$L$$$ and $$$R$$$. Divide the array into minimum number of sub-arrays such that each subarray have sum in the range $$$[L, R]$$$.

I thought of two pointers approach but I am sure how to take care of the lower bound of $$$L$$$ on subarray sum. How should we approach this problem?

I have a confusion about HackerCup 2021 Round 1 official solutions for problem A3 here.

Please read the problem statement here if you have not read it already.

I tried to run one of the inputs in both expanded form (after all K updates have been done) and in "concise form" here, I expected the outputs to be same by it seems the outputs are different for expanded and concise form for that specific input at least and I am not able to understand why. It would be helpful if someone can explain to me why the program is giving different outputs?

Thanks in advance.

The following problem was asked in a hiring challenge : -

Given an array $$$A$$$ of $$$N$$$ elements. All elements are distinct. The array is $$$1$$$-indexed.

You have $$$Q$$$ queries to answer. In the $$$i_{th}$$$ query, you are given three values $$$(X[i], L[i], R[i])$$$ and you should find the index $$$K$$$ such that

• $$$L[i]<=K<=R[i]$$$ and

• $$$A[K] \oplus X[i]$$$ is minimum where $$$\oplus$$$ is the bitwise XOR.

It is guaranteed that the value of $$$K$$$ will be unique for each query.

You task is to print the sum of the indices $$$K$$$ among all queries. Since the answer might be large, return it modulo $$$10^9+7$$$.

Constraints

$$$0<=N<10^5\newline0<=A[i]<=10^5\newline1<=Q<=10^5\newline0<=X[i]<=10^6\newline1<=L[i]<=R[i]<=N$$$

This question was asked in a hiring challenge. I have tried to do ascending sort based rightmost greater bit and then in each query do binary search for each bit starting from rightmost bit but I can't get that idea working even on paper. Can someone help me out with this problem as I am stuck? Any help would be greatly appreciated.

Problem statement

Moin Akhtar wants to come to Hackerland for his next harmonium performance. So, you decided to check how good he is at the harmonium. Moin's harmonium has N keys and each key has a number written on it. You asked him Q queries in each query you gave him a number X. He has to tell is there any key available in the harmonium such that bitwise and (&) of X and that key comes out to be 0.

Input Format:

1. the First Line contains an integer N denoting the number of keys in the harmonium

2. Second-line contains an array Key of size N denoting the value written on each key of the harmonium

3. Third-line Contains an integer Q denoting the number of queries.

Each of the next Q lines contains an integer X (described in the problem statement.)

OUTPUT FORMAT

For each Query, Print "Yes" or "Not in a new line, passed fit whether there is a key such that Key_j & X = 0

Constraints

1<=N,Q,X<=10^5

1<=Key_i<=10^5

Sample Input

3

1 2 3

5

1

2

3

4

5

Sample Output

Yes

Yes

No

Yes

Yes