Java solution using HashMap O(n)


#1

public class Solution {

public int solve(ArrayList<Integer> A, int B) {

    //|--------xor-----|
    //|------y-----|-k-|
    
    // y^k = xor
    // y = xor^k
    // No. of times y appears == count
    
    //TC - O(n)
    int count = 0;
    
    HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
    
    int xor = 0;
    for(int i  = 0; i< A.size(); i++ ){
        
        xor ^= A.get(i);
        
        if(xor==B){
            
            count ++;
        }
        int y = xor^B;
        
        if(hm.containsKey(y)){
            
            
            count += hm.get(y);
        }
            
        hm.put(xor,hm.getOrDefault(xor,0)+1);  // saving current xor value as prev - y
      
    }
    return count;
}

}
// brute force solution

// int xor = 0;
// int n = A.size();
// int count = 0;
// // traverse for all possible
// // subarrays
// for (int i = 0; i < n; i++)
// {
// int x = 0;
// for (int j = i; j < n; j++)
// {
// x ^= A.get(j);

// // if count of odd numbers
// // in subarray is m
// if (x == B)
// count++;
// }
// }

// return count;
// }
// }