Number of subsets with same AND , OR and XOR values in an Array | C ++ program to find the number of subsets with equal bitwise AND , OR and XOR values ; Function to find the number of subsets with equal bitwise AND , OR and XOR values ; Precompute the modded powers of two for subset counting ; Loop to iterate and find the modded powers of two for subset counting ; Map to store the frequency of each element ; Loop to compute the frequency ; For every element > 0 , the number of subsets formed using this element only is equal to 2 ^ ( frequency [ element ] - 1 ) . And for 0 , we have to find all the subsets , so 2 ^ ( frequency [ element ] ) - 1 ; If element is greater than 0 ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int mod = 1000000007 ; int countSubsets ( int a [ ] , int n ) { int answer = 0 ; int powerOfTwo [ 100005 ] ; powerOfTwo [ 0 ] = 1 ; for ( int i = 1 ; i < 100005 ; i ++ ) powerOfTwo [ i ] = ( powerOfTwo [ i - 1 ] * 2 ) % mod ; unordered_map < int , int > frequency ; for ( int i = 0 ; i < n ; i ++ ) frequency [ a [ i ] ] ++ ; for ( auto el : frequency ) { if ( el . first != 0 ) answer = ( answer % mod + powerOfTwo [ el . second - 1 ] ) % mod ; else answer = ( answer % mod + powerOfTwo [ el . second ] - 1 + mod ) % mod ; } return answer ; } int main ( ) { int N = 6 ; int A [ N ] = { 1 , 3 , 2 , 1 , 2 , 1 } ; cout << countSubsets ( A , N ) ; return 0 ; }