Noble integers in an array ( count of greater elements is equal to value ) | C ++ program to find Noble elements in an array . ; Declare a countArr which keeps count of all elements greater than or equal to arr [ i ] . Initialize it with zero . ; Iterating through the given array ; If current element is less than zero , it cannot be a solution so we skip it . ; If current element is >= size of input array , if will be greater than all elements which can be considered as our solution , as it cannot be greater than size of array . ; Else we increase the count of elements >= our current array in countArr ; Initially , countArr [ n ] is count of elements greater than all possible solutions ; Iterating through countArr ; If totalGreater = current index , means we found arr [ i ] for which count of elements >= arr [ i ] is equal to arr [ i ] ; If at any point count of elements greater than arr [ i ] becomes more than current index , then it means we can no longer have a solution ; Adding count of elements >= arr [ i ] to totalGreater . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int nobleInteger ( int arr [ ] , int n ) { int countArr [ n + 1 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] < 0 ) { continue ; } else if ( arr [ i ] >= n ) { countArr [ n ] ++ ; } else { countArr [ arr [ i ] ] ++ ; } } int totalGreater = countArr [ n ] ; for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( totalGreater == i && countArr [ i ] > 0 ) { return i ; } else if ( totalGreater > i ) { return -1 ; } totalGreater += countArr [ i ] ; } return -1 ; } int main ( ) { int arr [ ] = { 10 , 3 , 20 , 40 , 2 } ; int res = nobleInteger ( arr , 5 ) ; if ( res != -1 ) cout << " The ▁ noble ▁ integer ▁ is ▁ " << res ; else cout << " No ▁ Noble ▁ Integer ▁ Found " ; return 0 ; }