Mystical Numbers XORGAND Solution Codechef

by

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:

Leave a Comment

four × one =