Mystical Numbers XORGAND Solution Codechef
A number M is said to be a Mystical Number with respect to a number X if (M⊕X)>(M&X). You are given an array A of size N. You are also given Q queries. Each query consists of three integers L, R, and X.
For each query, find the count of Mystical Numbers in the subarray A[L:R] with respect to the number X.
Notes:
- ⊕ represents the Bitwise XOR operation and & represents the Bitwise AND operation.
- A[L:R] denotes the subarray A[L],A[L+1],…,A[R].
Input Format
- The first line contains a single integer T – the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N – the size of the array A.
- The second line of each test case contains N space-separated integers A1,A2,…,AN denoting the array A.
- The third line of each test case contains an integer Q – denoting the number of queries.
- The ith of the next Q lines contains three space-separated integers L , R and 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] with respect to the number X.
Constraints
- 1≤T≤100
- 1≤N≤2⋅105
- 0≤Ai<231
- 1≤Q≤2⋅105
- 1≤L≤R≤N
- 0≤X<231
- Sum of N over all test cases does not exceed 2⋅105.
- Sum of Q over all test cases does not exceed 2⋅105.
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:
Query 1: L=1,R=5,X=4.
A1⊕X=5,A1&X=0.
A2⊕X=6,A2&X=0.
A3⊕X=7,A3&X=0.
A4⊕X=0,A4&X=4.
A5⊕X=1,A5&X=4.
Mystical numbers are A1,A2, and A3 with respect to 4. Therefore, the answer to this query is 3.
Query 2: L=2,R=5,X=2.
A2⊕X=0,A2&X=2.
A3⊕X=1,A3&X=2.
A4⊕X=6,A4&X=0.
A5⊕X=7,A5&X=0.
Mystical numbers are A4 and A5 with respect to 2. Therefore , the answer to this query is 2.
SOLUTION
Program: Mystical Numbers XORGAND Solution Codechef in Python
import math
for _ in range(int(input())):
n = int(input())
arr = list(map(int, input().split()))
memo = [[0] for i in range(32)]
arrr = [None]+[int(math.log(i,2))+1 if i != 0 else 0 for i in arr]
for i in range(32):
for j in range(1, n+1):
if i == arrr[j] :
memo[i].append(memo[i][-1])
else:
memo[i].append((memo[i][-1]+1))
for _ in range(int(input())):
l, r, x = map(int, input().split())
x = int(math.log(x,2))+1 if x != 0 else 0
print(memo[x][r]-memo[x][l-1])
Program: Mystical Numbers XORGAND Solution Codechef in C++
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
int dp[n+1][33];
for(int i=1;i<=n;i++)
{
int temp=arr[i-1];
for(int j=0;j<33;j++){
dp[i][j]=dp[i-1][j];
}
int pwr=32;
if(temp!=0){
pwr=int(log2(temp));
}
dp[i][pwr]++;
}
int q;
cin>>q;
while(q--){
int l,r,x;
cin>>l>>r>>x;
int cnt=0;
int pwr=32;
if(x!=0){
pwr=int(log2(x));
}
cnt=dp[r][pwr]-dp[l-1][pwr];
int ans=(r-l+1)-cnt;
cout<<ans<<endl;
}
}
return 0;
}
Program: Mystical Numbers XORGAND Solution Codechef in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
int dp[][] = new int[n+1][33];
for (int i=1;i<=n;i++){
int temp = arr[i-1];
for(int j=0;j<33;j++){
dp[i][j] = dp[i-1][j];
}
int pwr = 32;
if(temp!=0) pwr = (int)(Math.log(temp)/Math.log(2));
dp[i][pwr] ++;
}
int q=sc.nextInt();
for(int i=0;i<q;i++)
{
int si=sc.nextInt();
int ei=sc.nextInt();
int x=sc.nextInt();
int cnt=0;
int pwr=32;
if(x!=0)pwr=(int)(Math.log(x)/Math.log(2));
cnt=dp[ei][pwr]-dp[si-1][pwr];
int ans=(ei-si+1)-cnt;
System.out.println(ans);
}
}
}
}
Related:
- The Magical Stone Solution Codechef
- Alternating Diameter ALTDIA Solution Codechef
- Pushpa PUSH7PA Solution Codechef
- The Attack of Queen Solution Codechef
- Sugarcane Juice Business Solution Codechef
- In The Green Zone ITGRZN Solution Codechef
- Four Arrays FOURARR Solution Codechef
- Miami GP F1RULE Solution Codechef
- Football Cup FOOTCUP Solution Codechef