Count elements such that there are exactly X elements with values greater than or equal to X

Hello Everyone,

Given an array arr of N integers, the task is to find the number of elements that satisfy the following condition:
If the element is X then there has to be exactly X number of elements in the array (excluding the number X ) which are greater than or equal to X

Examples:

Input: arr[] = {1, 2, 3, 4} Output: 1 Only element 2 satisfies the condition as there are exactly 2 elements which are greater than or equal to 2 (3, 4) except 2 itself. Input: arr[] = {5, 5, 5, 5, 5} Output: 0

Approach: The problem involves efficient searching for each arr[i] element the number of arr[j]’s (i != j) which are greater than or equal to arr[i].

• Sort the array in ascending order.
• For every element arr[i], using binary search get the count of all the elements that are greater than or equal to arr[i] except arr[i] itself.
• If the count is equal to arr[i] then increment the result.
• Print the value of the result in the end.

Below is the implementation of the above approach:

• C++

`// C++ implementation of the approach`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`#define ll long long`

` `

`ll ` `int` `getCount(vector<ll ` `int` `> v, ` `int` `n)`

`{`

` ` `// Sorting the vector`

` ` `sort((v).begin(), (v).end());`

` ` `ll ` `int` `cnt = 0;`

` ` `for` `(ll ` `int` `i = 0; i < n; i++) {`

` `

` ` `// Count of numbers which`

` ` `// are greater than v[i]`

` ` `ll ` `int` `tmp = v.end() - 1`

` ` `- upper_bound((v).begin(), (v).end(), v[i] - 1);`

` `

` ` `if` `(tmp == v[i])`

` ` `cnt++;`

` ` `}`

` ` `return` `cnt;`

`}`

` `

`// Driver code`

`int` `main()`

`{`

` ` `ll ` `int` `n;`

` ` `n = 4;`

` ` `vector<ll ` `int` `> v;`

` ` `v.push_back(1);`

` ` `v.push_back(2);`

` ` `v.push_back(3);`

` ` `v.push_back(4);`

` `

` ` `cout << getCount(v, n);`

` ` `return` `0;`

`}`

Output:

1