[Solution] Mystical Numbers solution codechef

Mystical Numbers solution codechef – A number MM is said to be a Mystical Number with respect to a number XX if (MX)>(M&X)(M⊕X)>(M&X).

[Solution] Mystical Numbers solution codechef

You are given an array AA of size NN. You are also given QQ queries. Each query consists of three integers LLRR, and XX.

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

Notes:

  •  represents the Bitwise XOR operation and && 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],…,A[R].

Input Format

  • The first line contains a single integer TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains an integer NN – the size of the array AA.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN denoting the array AA.
  • The third line of each test case contains an integer QQ – denoting the number of queries.
  • The ithith of the next QQ lines contains three space-separated integers LL , RR and XX.

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],…,A[R] with respect to the number XX.

[Solution] Mystical Numbers solution codechef

  • 1T1001≤T≤100
  • 1N21051≤N≤2⋅105
  • 0Ai<2310≤Ai<231
  • 1Q21051≤Q≤2⋅105
  • 1LRN1≤L≤R≤N
  • 0X<2310≤X<231
  • Sum of NN over all test cases does not exceed 21052⋅105.
  • Sum of QQ over all test cases does not exceed 21052⋅105.

Sample Input 1 

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

Sample Output 1 

3
2

Mystical Numbers solution Explanation

Test case 11:

  • Query 11L=1,R=5,X=4L=1,R=5,X=4.
    • A1X=5,A1&X=0A1⊕X=5,A1&X=0.
    • A2X=6,A2&X=0A2⊕X=6,A2&X=0.
    • A3X=7,A3&X=0A3⊕X=7,A3&X=0.
    • A4X=0,A4&X=4A4⊕X=0,A4&X=4.
    • A5X=1,A5&X=4A5⊕X=1,A5&X=4.

Mystical numbers are A1,A2,A1,A2, and A3A3 with respect to 44. Therefore, the answer to this query is 33.

  • Query 22L=2,R=5,X=2L=2,R=5,X=2.
    • A2X=0,A2&X=2A2⊕X=0,A2&X=2.
    • A3X=1,A3&X=2A3⊕X=1,A3&X=2.
    • A4X=6,A4&X=0A4⊕X=6,A4&X=0.
    • A5X=7,A5&X=0A5⊕X=7,A5&X=0.

Mystical numbers are A4A4 and A5A5 with respect to 22. Therefore , the answer to this query is 22.

For Solution

Click here

Leave a Comment