Find number of subarrays with XOR value a power of 2 | C ++ Program to count number of subarrays with Bitwise - XOR as power of 2 ; Function to find number of subarrays ; Hash Map to store prefix XOR values ; When no element is selected ; Check for all the powers of 2 , till a MAX value ; Insert Current prefixxor in Hash Map ; Driver Code
#include <bits/stdc++.h> NEW_LINE #define ll  long long int NEW_LINE #define MAX  10 NEW_LINE using namespace std ; int findSubarray ( int array [ ] , int n ) { unordered_map < int , int > mp ; mp . insert ( { 0 , 1 } ) ; int answer = 0 ; int preXor = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int value = 1 ; preXor ^= array [ i ] ; for ( int j = 1 ; j <= MAX ; j ++ ) { int Y = value ^ preXor ; if ( mp . find ( Y ) != mp . end ( ) ) { answer += mp [ Y ] ; } value *= 2 ; } if ( mp . find ( preXor ) != mp . end ( ) ) { mp [ preXor ] ++ ; } else { mp . insert ( { preXor , 1 } ) ; } } return answer ; } int main ( ) { int array [ ] = { 2 , 6 , 7 , 5 , 8 } ; int n = sizeof ( array ) / sizeof ( array [ 0 ] ) ; cout << findSubarray ( array , n ) << endl ; return 0 ; }