Given two arrays X[] and Y[] of positive integers, find the number of pairs such that x^y > y^x where x is an element from X[] and y is an element from Y[].
Examples:
Input: X[] = {2, 1, 6}, Y = {1, 5}
Output: 3
Explanation:
The 3 possible pairs are:
(2, 1) => 21 > 12
(2, 5) => 25 (= 32) > 52 (= 25)
(6, 1) => 61 > 16
Input: X[] = {10, 19, 18}, Y[] = {11, 15, 9}
Output: 2
Explanation:
The possible pairs are (10, 11) and (10, 15).
For Naive Approach [ O(M*N) ] and [ O(N logN + M logN) ] approach, please refer Set 1 of this article.
Efficient Approach: The above two approaches can be further optimized in O(N) time complexity.
This approach uses the concept of suffix sum to find the solution. We can observe that if y > x, then x^y > y^x. However, the following base cases and exceptions need to be considered:
- If x = 0, then count of possible y is 0.
- If x = 1, then count of possible y is the frequency of 0’s is the Y[] is the required answer.
- If x = 2, 23 < 32 and 24 = 42. Hence, for x = 2, we cannot have a valid pair with y = {2, 3, 4}. Hence, the sum of frequencies of 0, 1, and all numbers gt 4 in Y[] gives us the count of required valid pairs
- If x = 3, the sum of all frequencies except 3 in Y[] gives us the required count of possible pairs.
Follow the steps below to solve the problem:
- Store the frequencies of every element of Y array.
- Store the suffix sum of the array containing the frequencies.
- For every element x in X[] which does not belong to any of the base cases, the possible number of y’s will be suffix[x+1] + count of 0’s in Y[] + count of 1’s in Y[]. For the base cases, compute the pairs accordingly as discussed above.
- Print the total count of pairs.
Below is the implementation of the above approach:
C++
// C++ program to finds the number of// pairs (x, y) from X[] and Y[]// such that x^y > y^x#include <bits/stdc++.h>using namespace std;// Function to return the count of pairsint countPairs(int X[], int Y[], int m, int n){ vector<int> suffix(1005); long long total_pairs = 0; for (int i = 0; i < n; i++) suffix[Y[i]]++; // Compute suffix sums till i = 3 for (int i = 1e3; i >= 3; i--) suffix[i] += suffix[i + 1]; for (int i = 0; i < m; i++) { // Base Case: x = 0 if (X[i] == 0) // No valid pairs continue; // Base Case: x = 1 else if (X[i] == 1) { // Store the count of 0's total_pairs += suffix[0]; continue; } // Base Case: x = 2 else if (X[i] == 2) // Store suffix sum upto 5 total_pairs += suffix[5]; // Base Case: x = 3 else if (X[i] == 3) // Store count of 2 and // suffix sum upto 4 total_pairs += suffix[2] + suffix[4]; // For all other values of x else total_pairs += suffix[X[i] + 1]; // For all x >=2, every y = 0 // and every y = 1 makes a valid pair total_pairs += suffix[0] + suffix[1]; } // Return the count of pairs return total_pairs;}// Driver Programint main(){ int X[] = { 10, 19, 18 }; int Y[] = { 11, 15, 9 }; int m = sizeof(X) / sizeof(X[0]); int n = sizeof(Y) / sizeof(Y[0]); cout << countPairs(X, Y, m, n); return 0;} |
Java
// Java program to finds the number of// pairs (x, y) from X[] and Y[]// such that x^y > y^xclass GFG{ // Function to return the count of pairsstatic int countPairs(int X[], int Y[], int m, int n){ int []suffix = new int[1005]; long total_pairs = 0; for(int i = 0; i < n; i++) suffix[Y[i]]++; // Compute suffix sums till i = 3 for(int i = (int)1e3; i >= 3; i--) suffix[i] += suffix[i + 1]; for(int i = 0; i < m; i++) { // Base Case: x = 0 if (X[i] == 0) // No valid pairs continue; // Base Case: x = 1 else if (X[i] == 1) { // Store the count of 0's total_pairs += suffix[0]; continue; } // Base Case: x = 2 else if (X[i] == 2) // Store suffix sum upto 5 total_pairs += suffix[5]; // Base Case: x = 3 else if (X[i] == 3) // Store count of 2 and // suffix sum upto 4 total_pairs += suffix[2] + suffix[4]; // For all other values of x else total_pairs += suffix[X[i] + 1]; // For all x >=2, every y = 0 // and every y = 1 makes a valid pair total_pairs += suffix[0] + suffix[1]; } // Return the count of pairs return (int) total_pairs;} // Driver codepublic static void main(String[] args){ int X[] = { 10, 19, 18 }; int Y[] = { 11, 15, 9 }; int m = X.length; int n = Y.length; System.out.print(countPairs(X, Y, m, n));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to finds the number of# pairs (x, y) from X[] and Y[]# such that x^y > y^x# Function to return the count of pairsdef countPairs(X, Y, m, n): suffix = [0] * 1005 total_pairs = 0 for i in range(n): suffix[Y[i]] += 1 # Compute suffix sums till i = 3 for i in range(int(1e3), 2, -1 ): suffix[i] += suffix[i + 1] for i in range(m): # Base Case: x = 0 if(X[i] == 0): # No valid pairs continue # Base Case: x = 1 elif(X[i] == 1): # Store the count of 0's total_pairs += suffix[0] continue # Base Case: x = 2 elif(X[i] == 2): # Store suffix sum upto 5 total_pairs += suffix[5] # Base Case: x = 3 elif(X[i] == 3): # Store count of 2 and # suffix sum upto 4 total_pairs += (suffix[2] + suffix[4]) # For all other values of x else: total_pairs += suffix[X[i] + 1] # For all x >=2, every y = 0 # and every y = 1 makes a valid pair total_pairs += suffix[0] + suffix[1] # Return the count of pairs return total_pairs# Driver codeif __name__ == '__main__': X = [ 10, 19, 18 ] Y = [ 11, 15, 9 ] m = len(X) n = len(Y) print(countPairs(X, Y, m, n))# This code is contributed by Shivam Singh |
C#
// C# program to finds the number of// pairs (x, y) from []X and []Y// such that x^y > y^xusing System;class GFG{ // Function to return the count of pairs static int countPairs(int[] X, int[] Y, int m, int n) { int[] suffix = new int[1005]; long total_pairs = 0; for (int i = 0; i < n; i++) suffix[Y[i]]++; // Compute suffix sums till i = 3 for (int i = (int)1e3; i >= 3; i--) suffix[i] += suffix[i + 1]; for (int i = 0; i < m; i++) { // Base Case: x = 0 if (X[i] == 0) // No valid pairs continue; // Base Case: x = 1 else if (X[i] == 1) { // Store the count of 0's total_pairs += suffix[0]; continue; } // Base Case: x = 2 else if (X[i] == 2) // Store suffix sum upto 5 total_pairs += suffix[5]; // Base Case: x = 3 else if (X[i] == 3) // Store count of 2 and // suffix sum upto 4 total_pairs += suffix[2] + suffix[4]; // For all other values of x else total_pairs += suffix[X[i] + 1]; // For all x >=2, every y = 0 // and every y = 1 makes a valid pair total_pairs += suffix[0] + suffix[1]; } // Return the count of pairs return (int)total_pairs; } // Driver code public static void Main(String[] args) { int[] X = {10, 19, 18}; int[] Y = {11, 15, 9}; int m = X.Length; int n = Y.Length; Console.Write(countPairs(X, Y, m, n)); }}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program to implement// the above approach// Function to return the count of pairsfunction countPairs(X, Y, m, n){ let suffix = Array.from({length: 1005}, (_, i) => 0); let total_pairs = 0; for(let i = 0; i < n; i++) suffix[Y[i]]++; // Compute suffix sums till i = 3 for(let i = 1e3; i >= 3; i--) suffix[i] += suffix[i + 1]; for(let i = 0; i < m; i++) { // Base Case: x = 0 if (X[i] == 0) // No valid pairs continue; // Base Case: x = 1 else if (X[i] == 1) { // Store the count of 0's total_pairs += suffix[0]; continue; } // Base Case: x = 2 else if (X[i] == 2) // Store suffix sum upto 5 total_pairs += suffix[5]; // Base Case: x = 3 else if (X[i] == 3) // Store count of 2 and // suffix sum upto 4 total_pairs += suffix[2] + suffix[4]; // For all other values of x else total_pairs += suffix[X[i] + 1]; // For all x >=2, every y = 0 // and every y = 1 makes a valid pair total_pairs += suffix[0] + suffix[1]; } // Return the count of pairs return total_pairs;}// Driver code let X = [ 10, 19, 18 ]; let Y = [ 11, 15, 9 ]; let m = X.length; let n = Y.length; document.write(countPairs(X, Y, m, n)); // This code is contributed by susmitakundugoaldanga.</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
