Count pairs in an array such that frequency of one is at least value of other
Given an array A[] of integers. The task is to find the total number of ordered pairs of positive integers (X, Y) such that X occurs in A[] at least Y times and Y occurs in A at least X times.
Examples:
Input : A[] = { 1, 1, 2, 2, 3 } Output : 4 Ordered pairs are -> { [1, 1], [1, 2], [2, 1], [2, 2] } Input : A = { 3, 3, 2, 2, 2 } Output : 3 Ordered pairs are -> { [3, 2], [2, 2], [2, 3] }
Approach:
- Create a hash table m[] of count of elements of array A[].
- Traverse the hash table of unique elements. Let X be current key in the hash table Y be its frequency.
- Check for each element j = (1 to Y) such that, if m[ j ] >= X increment answer by 1.
- Return the count of total ordered pairs (X, Y) of array A.
Below is the implementation of above approach:
C++
// C++ program to find number // of ordered pairs #include <bits/stdc++.h> using namespace std; // Function to find count of Ordered pairs int countOrderedPairs( int A[], int n) { // Initialize pairs to 0 int orderedPairs = 0; // Store frequencies unordered_map< int , int > m; for ( int i = 0; i < n; ++i) m[A[i]]++; // Count total Ordered_pairs for ( auto entry : m) { int X = entry.first; int Y = entry.second; for ( int j = 1; j <= Y; j++) { if (m[j] >= X) orderedPairs++; } } return orderedPairs; } // Driver Code int main() { int A[] = { 1, 1, 2, 2, 3 }; int n = sizeof (A) / sizeof (A[0]); cout << countOrderedPairs(A, n); return 0; } |
Java
// Java program to find number // of ordered pairs import java.util.HashMap; import java.util.Map; class GFG { // Function to find count of Ordered pairs public static int countOrderedPairs( int [] A, int n) { // Initialize pairs to 0 int orderedPairs = 0 ; // Store frequencies HashMap<Integer, Integer> m = new HashMap<>(); for ( int i = 0 ; i < n; i++) { if (m.get(A[i]) == null ) m.put(A[i], 1 ); else { int a = m.get(A[i]); m.put(A[i], ++a); } } // Count total Ordered_pairs for ( int entry : m.keySet()) { int X = entry; int Y = m.get(entry); for ( int j = 1 ; j <= Y; j++) { if (m.get(j) >= X) orderedPairs++; } } return orderedPairs; } // Driver Code public static void main(String[] args) { int [] A = { 1 , 1 , 2 , 2 , 3 }; int n = A.length; System.out.print(countOrderedPairs(A, n)); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 program to find the # number of ordered pairs from collections import defaultdict # Function to find count of Ordered pairs def countOrderedPairs(A, n): # Initialize pairs to 0 orderedPairs = 0 # Store frequencies m = defaultdict( lambda : 0 ) for i in range ( 0 , n): m[A[i]] + = 1 # Count total Ordered_pairs for X,Y in m.items(): for j in range ( 1 , Y + 1 ): if m[j] > = X: orderedPairs + = 1 return orderedPairs # Driver Code if __name__ = = "__main__" : A = [ 1 , 1 , 2 , 2 , 3 ] n = len (A) print (countOrderedPairs(A, n)) # This code is contributed by Rituraj Jain |
C#
// C# program to illustrate how // to create a dictionary using System; using System.Collections.Generic; class GFG { // Function to find count of Ordered pairs public static int countOrderedPairs( int [] A, int n) { // Initialize pairs to 0 int orderedPairs = 0; // Store frequencies Dictionary< int , int > m = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { if (!m.ContainsKey(A[i])) m.Add(A[i], 1); else { m[A[i]]++; } } // Count total Ordered_pairs foreach (KeyValuePair< int , int > entry in m) { int X = entry.Key; int Y = entry.Value; for ( int j = 1; j <= Y; j++) { if (m[j] >= X) orderedPairs++; } } return orderedPairs; } // Driver Code public static void Main() { int [] A = {1, 1, 2, 2, 3}; int n = A.Length; Console.Write(countOrderedPairs(A, n)); } } // This code is contributed by // mohit kumar |
Javascript
<script> // JavaScript program to find number // of ordered pairs // Function to find count of Ordered pairs function countOrderedPairs(A, n) { // Initialize pairs to 0 let orderedPairs = 0; // Store frequencies let m = new Map(); for (let i = 0; i < n; ++i){ if (m.has(A[i])){ m.set(A[i],m.get(A[i])+1); } else m.set(A[i],1); } // Count total Ordered_pairs for (let [key,value] of m) { let X = key; let Y = value; for (let j = 1; j <= Y; j++) { if (m.get(j) >= X) orderedPairs++; } } return orderedPairs; } // Driver Code let A =[ 1, 1, 2, 2, 3 ]; let n = A.length; document.write(countOrderedPairs(A, n)); // This code is contributed by shinjanpatra </script> |
Output
4
Complexity Analysis:
- Time Complexity: O(n), for traversing inside map key-value pairs
- Auxiliary Space: O(n), to create a map of size n
Contact Us