Mystical Numbers CodeChef Solution | CodeChef Problem Solution 2022

Mystical Numbers CodeChef Solution | CodeChef Problem Solution 2022

A number M$M$ is said to be a Mystical Number with respect to a number X$X$ if (M⊕X)>(M&X)$(M\oplus X)>(M\mathrm{\&}X)$.

You are given an array A$A$ of size N$N$. You are also given Q$Q$ queries. Each query consists of three integers L$L$, R$R$, and X$X$.

For each query, find the count of Mystical Numbers in the subarray A[L:R]$A[L:R]$ with respect to the number X$X$.

Solution Click Below:-  CLICK HERE

Notes:

• ⊕$\oplus$ represents the Bitwise XOR operation and &$\mathrm{\&}$ represents the Bitwise AND operation.
• A[L:R]$A[L:R]$ denotes the subarray A[L],A[L+1],…,A[R]$A[L],A[L+1],\dots ,A[R]$.

Input Format

• The first line contains a single integer T$T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N$N$ - the size of the array A$A$.

Four Arrays CodeChef Solution | CodeChef Problem Solution 2022

In The Green Zone CodeChef Solution | CodeChef Problem Solution 2022

Football Cup CodeChef Solution | CodeChef Problem Solution 2022

Miami GP CodeChef Solution | CodeChef Problem Solution 2022

Sugarcane Juice Business CodeChef Solution 

The Attack of Queen CodeChef Solution | CodeChef Problem Solution 2022

Pushpa CodeChef Solution | CodeChef Problem Solution 2022

Mystical Numbers CodeChef Solution | CodeChef Problem Solution 2022

Alternating Diameter CodeChef Solution | CodeChef Problem Solution 2022

The Magical Stone CodeChef Solution | CodeChef Problem Solution 2022

• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ denoting the array A$A$.
• The third line of each test case contains an integer Q$Q$ - denoting the number of queries.
• The ith$i^{th}$ of the next Q$Q$ lines contains three space-separated integers L$L$ , R$R$ and X$X$.

Output Format

For each testcase,

• For each query, print in a new line, the count of Mystical Numbers among A[L],A[L+1],…,A[R]$A[L],A[L+1],\dots ,A[R]$ with respect to the number X$X$.

Constraints

• 1≤T≤100$1\le T\le 100$
• 1≤N≤2⋅105$1\le N\le 2\cdot {10}^5$
• 0≤Ai<231$0\le A_i<2^{31}$
• 1≤Q≤2⋅105$1\le Q\le 2\cdot {10}^5$
• 1≤L≤R≤N$1\le L\le R\le N$
• 0≤X<231$0\le X<2^{31}$
• Sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.
• Sum of Q$Q$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Sample Input 1 

1
5
1 2 3 4 5
2
1 5 4
2 5 2

Sample Output 1 

3
2

Explanation

Test case 1$1$:

• Query 1$1$: L=1,R=5,X=4$L=1,R=5,X=4$.
  • A1⊕X=5,A1&X=0$A_1\oplus X=5,A_1\mathrm{\&}X=0$.
  • A2⊕X=6,A2&X=0$A_2\oplus X=6,A_2\mathrm{\&}X=0$.
  • A3⊕X=7,A3&X=0$A_3\oplus X=7,A_3\mathrm{\&}X=0$.
  • A4⊕X=0,A4&X=4$A_4\oplus X=0,A_4\mathrm{\&}X=4$.
  • A5⊕X=1,A5&X=4$A_5\oplus X=1,A_5\mathrm{\&}X=4$.

Mystical numbers are A1,A2,$A_1,A_2,$ and A3$A_3$ with respect to 4$4$. Therefore, the answer to this query is 3$3$.

• Query 2$2$: L=2,R=5,X=2$L=2,R=5,X=2$.
  • A2⊕X=0,A2&X=2$A_2\oplus X=0,A_2\mathrm{\&}X=2$.
  • A3⊕X=1,A3&X=2$A_3\oplus X=1,A_3\mathrm{\&}X=2$.
  • A4⊕X=6,A4&X=0$A_4\oplus X=6,A_4\mathrm{\&}X=0$.
  • A5⊕X=7,A5&X=0$A_5\oplus X=7,A_5\mathrm{\&}X=0$.

Mystical numbers are A4$A_4$ and A5$A_5$ with respect to 2$2$. Therefore , the answer to this query is 2$2$.

Join Now for Solution:-