Count array elements that can be maximized by adding any permutation of first N natural numbers | C ++ program for the above approach ; Comparator function to sort the given array ; Function to get the count of values that can have the maximum value ; Sort array in decreasing order ; Stores the answer ; mark stores the maximum value till each index i ; Check if arr [ i ] can be maximum ; Update the mark ; Print the total count ; Driver Code ; Given array arr [ ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool cmp ( int x , int y ) { return x > y ; } void countMaximum ( int * a , int n ) { sort ( a , a + n , cmp ) ; int count = 0 ; int mark = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( ( a [ i ] + n >= mark ) ) { count += 1 ; } mark = max ( mark , a [ i ] + i + 1 ) ; } cout << count ; } int main ( ) { int arr [ ] = { 8 , 9 , 6 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; countMaximum ( arr , N ) ; }