Number of subsets with same AND , OR and XOR values in an Array | Java 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
import java . util . * ; class GFG { static int mod = 1000000007 ; static int countSubsets ( int a [ ] , int n ) { int answer = 0 ; int [ ] powerOfTwo = new int [ 100005 ] ; powerOfTwo [ 0 ] = 1 ; for ( int i = 1 ; i < 100005 ; i ++ ) powerOfTwo [ i ] = ( powerOfTwo [ i - 1 ] * 2 ) % mod ; HashMap < Integer , Integer > frequency = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) if ( frequency . containsKey ( a [ i ] ) ) { frequency . put ( a [ i ] , frequency . get ( a [ i ] ) + 1 ) ; } else { frequency . put ( a [ i ] , 1 ) ; } for ( Map . Entry < Integer , Integer > el : frequency . entrySet ( ) ) { if ( el . getKey ( ) != 0 ) answer = ( answer % mod + powerOfTwo [ el . getValue ( ) - 1 ] ) % mod ; else answer = ( answer % mod + powerOfTwo [ el . getValue ( ) ] - 1 + mod ) % mod ; } return answer ; } public static void main ( String [ ] args ) { int N = 6 ; int A [ ] = { 1 , 3 , 2 , 1 , 2 , 1 } ; System . out . print ( countSubsets ( A , N ) ) ; } }