Size of the smallest subset with maximum Bitwise OR | Java Program for above approach ; Compute bitwise or of all elements in array of size sz ; Recursively calculating the size of minimum subset with maximum or ; If i is arr . length ; If curOr is equal to maxOr ; Return arr . length ; Try the current element in the subset ; Skip the current element ; Return minimum of take and notTake ; Driver Code ; Function Call
import java . io . * ; import java . util . * ; class Solution { private static int OR ( int [ ] arr ) { int mOR = 0 ; for ( int i = 0 ; i < arr . length ; ++ i ) { mOR |= arr [ i ] ; } return mOR ; } private static int maxSubset ( int [ ] arr , int i , int curOr , int curSize , int maxOr ) { if ( i == arr . length ) { if ( curOr == maxOr ) { return curSize ; } else { return arr . length ; } } int take = maxSubset ( arr , i + 1 , curOr arr [ i ] , curSize + 1 , maxOr ) ; int notTake = maxSubset ( arr , i + 1 , curOr , curSize , maxOr ) ; return Math . min ( take , notTake ) ; } public static void main ( String [ ] args ) { int [ ] data = { 5 , 1 , 3 , 4 , 2 } ; int maxOr = OR ( data ) ; int maxSubsetSize = maxSubset ( data , 0 , 0 , 0 , maxOr ) ; System . out . println ( maxSubsetSize ) ; } }