Sudo Placement | Placement Tour | CPP Program to find the optimal number of elements such that the cumulative value should be less than given number ; This function returns true if the value cumulative according to received integer K is less than budget B , otherwise returns false ; Initialize a temporary array which stores the cumulative value of the original array ; Sort the array to find the smallest K values ; Check if the value is less than budget ; This function prints the optimal number of elements and respective cumulative value which is less than the given number ; Initialize answer as zero as optimal value may not exists ; If the current Mid Value is an optimal value , then try to maximize it ; Call Again to set the corresponding cumulative value for the optimal ans ; Driver Code ; Budget
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool canBeOptimalValue ( int K , int arr [ ] , int N , int B , int & value ) { int tmp [ N ] ; for ( int i = 0 ; i < N ; i ++ ) tmp [ i ] = ( arr [ i ] + K * ( i + 1 ) ) ; sort ( tmp , tmp + N ) ; value = 0 ; for ( int i = 0 ; i < K ; i ++ ) value += tmp [ i ] ; return value <= B ; } void findNoOfElementsandValue ( int arr [ ] , int N , int B ) { int ans = 0 ; int cumulativeValue = 0 ; while ( start <= end ) { int mid = ( start + end ) / 2 ; if ( canBeOptimalValue ( mid , arr , N , B , cumulativeValue ) ) { ans = mid ; start = mid + 1 ; } else end = mid - 1 ; } canBeOptimalValue ( ans , arr , N , B , cumulativeValue ) ; cout << ans << " ▁ " << cumulativeValue << endl ; } int main ( ) { int arr [ ] = { 1 , 2 , 5 , 6 , 3 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int B = 90 ; findNoOfElementsandValue ( arr , N , B ) ; return 0 ; }