Find integers such that A contains exactly X distinct integers greater than A{i]
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 – ((u1, f1), (u2, f2)….(un, fn)) where fi is the frequency of element ui and u1 > u2 > ……un.
- For each i = 1 to n, there are i – 1 distinct integers that is greater than ui. So, for each X=0 to n-1 the answer for X would be fX+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++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; #define int long long // Function to Print the number of // integers i from 1 to N such that A // contains exactly X distinct integers // greater than A{i] void Solve( int N, int A[]) { // Declaring the hashmap mp map< int , int > mp; // Inserting elements of A into mp for ( int i = 0; i < N; i++) { mp[A[i]]++; } // Finding the size of map int n = ( int )mp.size(); // Printing the frequencies of // elements in map in reverse order for ( auto it = mp.rbegin(); it != mp.rend(); it++) { cout << it->second << " " ; } // Printing N-n zeroes for ( int i = 1; i <= N - n; i++) { cout << 0 << " " ; } } // Driver code int32_t main() { int N = 6; int A[] = { 2, 7, 1, 8, 2, 8 }; // Function Call Solve(N, A); return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG { // Function to Print the number of // integers i from 1 to N such that A // contains exactly X distinct integers // greater than A{i] static void Solve( int N, int A[]) { // Declaring the hashmap mp Map<Integer, Integer> mp = new HashMap<>(); // Inserting elements of A into mp for ( int i = 0 ; i < N; i++) { if (mp.containsKey(A[i])) { mp.put(A[i], mp.get(A[i]) + 1 ); } else { mp.put(A[i], 1 ); } } ArrayList<Integer> keys = new ArrayList<Integer>(mp.keySet()); // Finding the size of map int n = keys.size(); // Printing the frequencies of // elements in map in reverse order for ( int i=n- 1 ; i >= 0 ; i--){ System.out.print(mp.get(keys.get(i)) + " " ); } // Printing N-n zeroes for ( int i = 1 ; i <= N - n; i++) { System.out.print( "0 " ); } } // Driver code public static void main (String[] args) { int N = 6 ; int A[] = { 2 , 7 , 1 , 8 , 2 , 8 }; // Function Call Solve(N, A); } } |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class GFG { // Function to Print the number of // integers i from 1 to N such that A // contains exactly X distinct integers // greater than A{i] static void Solve( int N, int [] A) { // Declaring the hashmap mp Dictionary< int , int > mp = new Dictionary< int , int >(); // Inserting elements of A into mp for ( int i = 0; i < N; i++) { if (mp.ContainsKey(A[i])) { mp[A[i]]++; } else { mp[A[i]] = 1; } } // Finding the size of map int n = mp.Count; // Printing the frequencies of // elements in map in reverse order List< int > keys = new List< int >(mp.Keys); keys.Sort(); keys.Reverse(); foreach ( int key in keys) { Console.Write(mp[key] + " " ); } // Printing N-n zeroes for ( int i = 1; i <= N - n; i++) { Console.Write( "0 " ); } } // Driver code public static void Main() { int N = 6; int [] A = { 2, 7, 1, 8, 2, 8 }; // Function Call Solve(N, A); } } // this code is contributed by bhardwajji |
Javascript
// JavaScript code for the above approach function Solve(N, A){ // Declaring the dictionary mp let mp = {}; // Inserting elements of A into mp for (let i = 0; i < N; i++) { if (mp[A[i]]) { mp[A[i]]++; } else { mp[A[i]] = 1; } } // Finding the size of dictionary let n = Object.keys(mp).length; // Creating an array of frequencies of // elements in mp in reverse order let freqArr = []; for (let key in mp) { freqArr.push(mp[key]); } freqArr.reverse(); // Printing the frequencies of // elements in mp in reverse order console.log(freqArr.join( ' ' )+ " " ); // Printing N-n zeroes for (let i = 1; i <= N - n; i++) { console.log(0+ " " ); } } // Driver code let N = 6; let A = [2, 7, 1, 8, 2, 8]; // Function Call Solve(N, A); |
Python
def solve(N, A): # Declaring the dictionary mp mp = {} # Inserting elements of A into mp for i in range (N): if A[i] in mp: mp[A[i]] + = 1 else : mp[A[i]] = 1 # Finding the size of dictionary n = len (mp) # Creating an array of frequencies of elements in mp in reverse order freqArr = [] for key in mp: freqArr.append(mp[key]) # Printing the frequencies of elements in mp in reverse order print (( map ( str , freqArr))) # Printing N-n zeroes for i in range (N - n): print ( '0 ' ) # Driver code N = 6 A = [ 2 , 7 , 1 , 8 , 2 , 8 ] # Function call solve(N, A) |
2 1 2 1 0 0
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)