Maximum items that can be bought from the cost Array based on given conditions | C ++ program to find the maximum number of items that can be bought from the given cost array ; Function to find the maximum number of items that can be bought from the given cost array ; Sort the given array ; Variables to store the prefix sum , answer and the counter variables ; Initializing the first element of the prefix array ; If we can buy at least one item ; Iterating through the first K items and finding the prefix sum ; Check the number of items that can be bought ; Finding the prefix sum for the remaining elements ; Check the number of iteams that can be bought ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int number ( int a [ ] , int n , int p , int k ) { sort ( a , a + n ) ; int pre [ n ] = { 0 } , val , i , j , ans = 0 ; pre [ 0 ] = a [ 0 ] ; if ( pre [ 0 ] <= p ) ans = 1 ; for ( i = 1 ; i < k - 1 ; i ++ ) { pre [ i ] = pre [ i - 1 ] + a [ i ] ; if ( pre [ i ] <= p ) ans = i + 1 ; } pre [ k - 1 ] = a [ k - 1 ] ; for ( i = k - 1 ; i < n ; i ++ ) { if ( i >= k ) { pre [ i ] += pre [ i - k ] + a [ i ] ; } if ( pre [ i ] <= p ) ans = i + 1 ; } return ans ; } int main ( ) { int n = 5 ; int arr [ ] = { 2 , 4 , 3 , 5 , 7 } ; int p = 11 ; int k = 2 ; cout << number ( arr , n , p , k ) << endl ; return 0 ; }