Given an array arr[], the task is to count unordered pairs of positive integers (p, q) such that p occurs in the array at least q times and q occurs at least p times.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: 1
(1, 1) is the only valid pair.Input: arr[] = {3, 3, 2, 2, 2}
Output: 2
(2, 3) and (2, 2) are the only possible pairs.
Approach:
- The idea is to hash every element of an array with its count and create a vector of unique elements from the array elements. Initialize the number of pairs to 0.
- Loop through the vector of unique elements to count the number of pairs.
- Inside the loop, if the count of the element is less than the element itself, then continue, else if the count of the element is equal to the element, then increment the number of pairs by 1 (Pair of the form (x, x)), else go to Step 4.
- Increment the number of pairs by 1 and loop from j = (element + 1) to the count of the element updating j by 1 if the count of j is greater than or equal to an element, then increment the number of pairs by 1 as the pairs are unordered.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of required pairsint get_unordered_pairs(int a[], int n){ // To store unique elements vector<int> vs; // To hash elements with their frequency unordered_map<int, int> m; // Store frequencies in m and all distinct // items in vs for (int i = 0; i < n; i++) { m[a[i]]++; if (m[a[i]] == 1) vs.push_back(a[i]); } // Traverse through distinct elements int number_of_pairs = 0; for (int i = 0; i < vs.size(); i++) { // If current element is greater than // its frequency in the array if (m[vs[i]] < vs[i]) continue; // If element is equal to its frequency, // a pair of the form (x, x) is formed. else if (m[vs[i]] == vs[i]) number_of_pairs += 1; // If element is less than its frequency else { number_of_pairs += 1; for (int j = vs[i] + 1; j <= m[vs[i]]; j++) { if (m[j] >= vs[i]) number_of_pairs += 1; } } } return number_of_pairs;}// Driver codeint main(){ int arr[] = { 3, 3, 2, 2, 2 }; int n = sizeof(arr) / sizeof(arr[0]); cout << get_unordered_pairs(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Function to return the count of required pairsstatic int get_unordered_pairs(int []a, int n){ // To store unique elements ArrayList<Integer> vs = new ArrayList<Integer>(); // To hash elements with their frequency int[] m = new int[maximum(a)+1]; // Store frequencies in m and all distinct // items in vs for (int i = 0; i < n; i++) { m[(int)a[i]]++; if (m[a[i]] == 1) vs.add(a[i]); } // Traverse through distinct elements int number_of_pairs = 0; for (int i = 0; i < vs.size(); i++) { // If current element is greater than // its frequency in the array if (m[(int)vs.get(i)] < (int)vs.get(i)) continue; // If element is equal to its frequency, // a pair of the form (x, x) is formed. else if (m[(int)vs.get(i)] == (int)vs.get(i)) number_of_pairs += 1; // If element is less than its frequency else { number_of_pairs += 1; for (int j = (int)vs.get(i) + 1; j <= m[(int)vs.get(i)]; j++) { if (m[j] >= (int)vs.get(i)) number_of_pairs += 1; } } } return number_of_pairs;}static int maximum(int []arr){ int max = Integer.MIN_VALUE; for(int i = 0; i < arr.length; i++) { if(arr[i] > max) { max = arr[i]; } } return max;}// Driver codepublic static void main (String[] args) { int []arr = { 3, 3, 2, 2, 2 }; int n = arr.length; System.out.println(get_unordered_pairs(arr, n));}}// This code is contributed by mits |
Python3
# Python3 implementation of the approach from collections import defaultdict# Function to return the count of # required pairs def get_unordered_pairs(a, n): # To store unique elements vs = [] # To hash elements with their frequency m = defaultdict(lambda:0) # Store frequencies in m and # all distinct items in vs for i in range(0, n): m[a[i]] += 1 if m[a[i]] == 1: vs.append(a[i]) # Traverse through distinct elements number_of_pairs = 0 for i in range(0, len(vs)): # If current element is greater # than its frequency in the array if m[vs[i]] < vs[i]: continue # If element is equal to its frequency, # a pair of the form (x, x) is formed. elif m[vs[i]] == vs[i]: number_of_pairs += 1 # If element is less than its # frequency else: number_of_pairs += 1 for j in range(vs[i] + 1, m[vs[i]] + 1): if m[j] >= vs[i]: number_of_pairs += 1 return number_of_pairs # Driver code if __name__ == "__main__": arr = [3, 3, 2, 2, 2] n = len(arr) print(get_unordered_pairs(arr, n))# This code is contributed# by Rituraj Jain |
C#
// C# implementation of the approachusing System;using System.Collections;using System.Linq;class GFG{// Function to return the count of required pairsstatic int get_unordered_pairs(int []a, int n){ // To store unique elements ArrayList vs = new ArrayList(); // To hash elements with their frequency int[] m = new int[a.Max()+1]; // Store frequencies in m and all distinct // items in vs for (int i = 0; i < n; i++) { m[(int)a[i]]++; if (m[a[i]] == 1) vs.Add(a[i]); } // Traverse through distinct elements int number_of_pairs = 0; for (int i = 0; i < vs.Count; i++) { // If current element is greater than // its frequency in the array if (m[(int)vs[i]] < (int)vs[i]) continue; // If element is equal to its frequency, // a pair of the form (x, x) is formed. else if (m[(int)vs[i]] == (int)vs[i]) number_of_pairs += 1; // If element is less than its frequency else { number_of_pairs += 1; for (int j = (int)vs[i] + 1; j <= m[(int)vs[i]]; j++) { if (m[j] >= (int)vs[i]) number_of_pairs += 1; } } } return number_of_pairs;}// Driver codestatic void Main(){ int []arr = { 3, 3, 2, 2, 2 }; int n = arr.Length; Console.WriteLine(get_unordered_pairs(arr, n));}}// This code is contributed by mits |
PHP
<?php// PHP implementation of the approach // Function to return the count of // required pairs function get_unordered_pairs($a, $n) { // To store unique elements $vs = array(); // To hash elements with // their frequency $m = array(); for($i = 0; $i < $n; $i++) $m[$a[$i]] = 0 ; // Store frequencies in m and // all distinct items in vs for ($i = 0; $i < $n; $i++) { $m[$a[$i]]++; if ($m[$a[$i]] == 1) array_push($vs, $a[$i]); } // Traverse through distinct elements $number_of_pairs = 0; for ($i = 0; $i < sizeof($vs); $i++) { // If current element is greater // than its frequency in the array if ($m[$vs[$i]] < $vs[$i]) continue; // If element is equal to its frequency, // a pair of the form (x, x) is formed. else if ($m[$vs[$i]] == $vs[$i]) $number_of_pairs += 1; // If element is less than its // frequency else { $number_of_pairs += 1; for ($j = $vs[$i] + 1; $j <= $m[$vs[$i]]; $j++) { if ($m[$j] >= $vs[$i]) $number_of_pairs += 1; } } } return $number_of_pairs; } // Driver code $arr = array(3, 3, 2, 2, 2); $n = sizeof($arr);echo get_unordered_pairs($arr, $n); // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of the approach // Function to return the count of required pairsfunction get_unordered_pairs(a, n){ // To store unique elements let vs = []; // To hash elements with their frequency let m = Array.from({length: Math.max(...a)+1}, (_, i) => 0); // Store frequencies in m and all distinct // items in vs for (let i = 0; i < n; i++) { m[a[i]]++; if (m[a[i]] == 1) vs.push(a[i]); } // Traverse through distinct elements let number_of_pairs = 0; for (let i = 0; i < vs.length; i++) { // If current element is greater than // its frequency in the array if (m[vs[i]] < vs[i]) continue; // If element is equal to its frequency, // a pair of the form (x, x) is formed. else if (m[vs[i]] == vs[i]) number_of_pairs += 1; // If element is less than its frequency else { number_of_pairs += 1; for (let j = vs[i] + 1; j <= m[vs[i]]; j++) { if (m[j] >= vs[i]) number_of_pairs += 1; } } } return number_of_pairs;} // Driver code let arr = [ 3, 3, 2, 2, 2 ]; let n = arr.length; document.write(get_unordered_pairs(arr, n)); </script> |
Output:
2
Time Complexity: O(N* log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
