Maximize count of subsets having product of smallest element and size of the subset at least X | C ++ Program to implement the above approach ; Comparator function to return the greater of two numbers ; Function to return the maximum count of subsets possible which satisfy the above condition ; Sort the array in descending order ; Stores the count of subsets ; Stores the size of the current subset ; Check for the necessary conditions ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool comp ( int a , int b ) { return a > b ; } int maxSubset ( int arr [ ] , int N , int X ) { sort ( arr , arr + N , comp ) ; int counter = 0 ; int sz = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sz ++ ; if ( arr [ i ] * sz >= X ) { counter ++ ; sz = 0 ; } } return counter ; } int main ( ) { int arr [ ] = { 7 , 11 , 2 , 9 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int X = 10 ; cout << maxSubset ( arr , N , X ) ; }