STRIPE 90LPA CTC SDE-1 OA QUESTION WITH CODE -

C++ CODE :-

#include <bits/stdc++.h>
using namespace std;
using ll = long long; // SAB KUCH LL USE KARO SO THAT NO CONFUSION LOL 

int main() {
	int t; cin>>t; 
	while(t--){
	    ll N,K; cin>>N>>K;  // K>=0
	    vector<ll> arr(N); //array of 'N' non negative integers i.e. arr[i]>=0 for all index 'i'
	    for(ll i=0;i<N;i++) cin>>arr[i]; //take array input
	    
	    - //CONCEPT :-
	    - // i<j  --- eqn.1
	    - // Formulas to simplify the equation (LEARN THEM) :- 
	    - //a+b = (a^b) + 2(a&b) 
	    - //a+b = (a∣b) + (a&b)
	    - //a^b = (a∣b) − (a&b)
	    - // Simplified Eq'n : arr[j] = (K-arr[i]) ^ arr[i]  --- eqn.2
	    - //for any index 'i' we have to see index 'j' on the right side of index 'i' with arr[j] value = (K-arr[i])^arr[i]
	    - // so we traverse array from RIGHT TO LEFT so that we already know value of arr[j] (FUTURE) as we can store all values in hashmap for fast fetching 
	    
	    unordered_map<ll,ll> freq; // to store array elements value
	    freq[arr[N-1]]++; //last element ko daldo so that we can start i from 2nd last element i.e. n-2 kyuki we have to search for PAIRS satisfying eqn.1 and eqn.2
	    
	    ll no_of_pairs=0; //FINAL ANSWER i.e. no of pairs 
	    
	    for(ll i=N-2;i>=0;i--){  //start from 2nd last element i.e. index n-2 
	        ll y=K-arr[i];  
	        
	        if(y>=0){  //y should be non negative bcoz y=arr[j]^arr[i] and ( arr[j] XOR arr[i] ) will be non negative as array elements are non negative (given in Q.)
	            ll aj=y^arr[i];
	            no_of_pairs+=freq[aj]; //see how many elements(i.e. Frequency of elements with value aj) on right side with value aj and add their frequency 
	        }
	        freq[arr[i]]++; //now add this current element value to hashmap i.e. arr[i] so that we can use it for left side elements
	    }
	    
	    cout<<no_of_pairs<<'\n'; //FINAL ANSWER :)  
	}
    return 0;
}