Count of distinct possible pairs such that the element from A is greater than the element from B
Given two given arrays A and B of equal length, the task is to find the maximum number of distinct pairs of elements that can be chosen such that the element from A is strictly greater than the element from B.
Examples:
Input:
A[]={20, 30, 50} , B[]={25, 60, 40}
Output: 2
Explanation:
(30, 25) and (50, 40) are the two possible pairs.Input:
A[]={20, 25, 60} , B[]={25, 60, 40}
Output: 1
Explanation:
(60, 25) or (60, 40) can be the required pair.
Approach: In order to solve this problem, we need to adopt the following approach:
- Sort both the arrays.
- Traverse the entire length of array A and check if the current element in A is greater than the element in B currently pointed at B.
- If so, point to the next element in both the arrays. Otherwise, move to the next element in A and check if it is greater than the element currently pointed at B.
- The number of elements traversed in array B after the entire traversal of array A gives the required answer.
Illustration:
Let us consider the two following arrays:
A[] = {30, 28, 45, 22} , B[] = {35, 25, 22, 48}
After sorting, the arrays appear to be
A[] = {22, 28, 30, 45} , B[] = {22, 25, 35, 48}
After the first iteration, since A[0] is not greater than B[0], we move to A[1].
After the second iteration, we move to B[1] as A[1] is greater than B[0].
After the third iteration, we move to B[2] as A[2] is greater than B[1].
Similarly, A[3] is greater than B[2] and we move to B[3].
Hence, the number of elements traversed in B, i.e. 3, is the final answer.
The possible pairs are (28,22), (30,25), (45, 35).
Below is the implementation of the above approach:
C++
// C++ Program to count number of distinct // pairs possible from the two arrays // such that element selected from one array is // always greater than the one selected from // the other array #include <bits/stdc++.h> using namespace std; // Function to return the count // of pairs int countPairs(vector< int > A, vector< int > B) { int n = A.size(); sort(A.begin(),A.end()); sort(B.begin(),B.end()); int ans = 0, i; for ( int i = 0; i < n; i++) { if (A[i] > B[ans]) { ans++; } } return ans; } // Driver code int main() { vector< int > A = { 30, 28, 45, 22 }; vector< int > B = { 35, 25, 22, 48 }; cout << countPairs(A,B); return 0; } |
Java
// Java program to count number of distinct // pairs possible from the two arrays such // that element selected from one array is // always greater than the one selected from // the other array import java.util.*; class GFG{ // Function to return the count // of pairs static int countPairs( int [] A, int [] B) { int n = A.length; int ans = 0 ; Arrays.sort(A); Arrays.sort(B); for ( int i = 0 ; i < n; i++) { if (A[i] > B[ans]) { ans++; } } return ans; } // Driver code public static void main(String[] args) { int [] A = { 30 , 28 , 45 , 22 }; int [] B = { 35 , 25 , 22 , 48 }; System.out.print(countPairs(A, B)); } } // This code is contributed by sapnasingh4991 |
Python3
# Python3 program to count number of distinct # pairs possible from the two arrays # such that element selected from one array is # always greater than the one selected from # the other array # Function to return the count # of pairs def countPairs(A, B): n = len (A) A.sort() B.sort() ans = 0 for i in range (n): if (A[i] > B[ans]): ans + = 1 return ans # Driver code if __name__ = = '__main__' : A = [ 30 , 28 , 45 , 22 ] B = [ 35 , 25 , 22 , 48 ] print (countPairs(A, B)) # This code is contributed by Shivam Singh |
C#
// C# program to count number of distinct // pairs possible from the two arrays such // that element selected from one array is // always greater than the one selected from // the other array using System; class GFG{ // Function to return the count // of pairs static int countPairs( int [] A, int [] B) { int n = A.Length; int ans = 0; Array.Sort(A); Array.Sort(B); for ( int i = 0; i < n; i++) { if (A[i] > B[ans]) { ans++; } } return ans; } // Driver code public static void Main() { int []A = { 30, 28, 45, 22 }; int []B = { 35, 25, 22, 48 }; Console.Write(countPairs(A, B)); } } // This code is contributed by Code_Mech |
Javascript
<script> // Javascript program to count number of distinct // pairs possible from the two arrays such // that element selected from one array is // always greater than the one selected from // the other array // Function to return the count // of pairs function countPairs(A, B) { let n = A.length; let ans = 0; A.sort(); B.sort(); for (let i = 0; i < n; i++) { if (A[i] > B[ans]) { ans++; } } return ans; } // Driver Code let A = [ 30, 28, 45, 22 ]; let B = [ 35, 25, 22, 48 ]; document.write(countPairs(A, B)); </script> |
3
Time Complexity: O(n * log n)
Auxiliary Space: O(1)