Find integers such that A contains exactly X distinct integers greater than A{i]

By Ann Roberts On Feb 6, 2023

Given an array A[] of N integers, the task is to print the number of integers i from 1 to N, for which A contains exactly X distinct integers (for X = 0 to N-1) greater than Ai

Examples:

Input: N = 6, A[] = {2, 7, 1, 8, 2, 8}
Output: {2, 1, 2, 1, 0, 0}
Explanation: Let us consider X = 2.
A[1] = 2: A contains 2 distinct integers greater than 2 (7 and 8)
A[2] = 7: A contains 1 distinct integer greater than 7 (8)
A[3] = 1: A contains 3 distinct integers greater than 1 (2, 7 and 8)
A[4] = 8: A doesn’t contain any distinct integers greater than 8
A[5] = 2: A contains 2 distinct integers greater than 2 (7 and 8)
A[6] = 8: A doesn’t contain any distinct integers greater than 8
So, the given condition is satisfied for i=1 and 5 in case of X=2.

Input: N = 1, A[] = {1}
Output: 1

Approach: To solve the problem follow the below observations:

Observations:

If we store frequency of each element of array in a hashmap and sort it in decreasing order by the keys, then:

Let the hashmap be – ((u₁, f₁), (u₂, f₂)….(u_n, f_n)) where f_i is the frequency of element u_iand u1 > u2 > ……un.

For each i = 1 to n, there are i – 1 distinct integers that is greater than u_i. So, for each X=0 to n-1 the answer for X would be f_X+1.

Answer for X = n to N – 1 would be 0.

Based on the above observation following approach can be used to solve the problem:

Declare a map (say mp) and insert the elements of array A into it.
Iterate the map from the end and print the frequencies of the elements.
For the remaining elements (i.e. N-n), print N-n zeroes.

Following is the code based on the above approach :

C++

#include <bits/stdc++.h>

using namespace std;

#define int long long

void Solve(int N, int A[])

{

map<int, int> mp;

for (int i = 0; i < N; i++) {

mp[A[i]]++;

}

int n = (int)mp.size();

for (auto it = mp.rbegin(); it != mp.rend(); it++) {

cout << it->second << " ";

}

for (int i = 1; i <= N - n; i++) {

cout << 0 << " ";

}

int32_t main()

{

int N = 6;

int A[] = { 2, 7, 1, 8, 2, 8 };

Solve(N, A);

return 0;

}

Time Complexity: O(N*log(N))
Auxiliary Space: O(N)