Dadas dos arrays X[] e Y[] de enteros positivos, encuentre un número de pares tales que x^y > y^x donde x es un elemento de X[] e y es un elemento de Y[].
Ejemplos:
C++
long long countPairsBruteForce(long long X[], long long Y[],
long long m, long long n)
{
long long ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (pow(X[i], Y[j]) > pow(Y[j], X[i]))
ans++;
return ans;
}
Java
public static long countPairsBruteForce(long X[], long Y[],
int m, int n)
{
long ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (Math.pow(X[i], Y[j]) > Math.pow(Y[j], X[i]))
ans++;
return ans;
}
Python3
def countPairsBruteForce(X, Y, m, n): ans = 0 for i in range(m): for j in range(n): if (pow(X[i], Y[j]) > pow(Y[j], X[i])): ans += 1 return ans
C#
public static int countPairsBruteForce(int[] X, int[] Y,
int m, int n)
{
int ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (Math.Pow(X[i], Y[j]) > Math.Pow(Y[j], X[i]))
ans++;
return ans;
}
Javascript
function countPairsBruteForce(X, Y, m, n){
let ans = 0;
for(let i=0; i<m; i++ ){
for(let j=0;j<n;j++){
if ((Math.pow(X[i], Y[j]) > Math.pow(Y[j], X[i]))){
ans += 1;
}
}
}
return ans;
}
Complejidad de tiempo : O (M * N) donde M y N son tamaños de arrays dadas.
Solución eficiente:
El problema se puede resolver en tiempo O(nLogn + mLogn) . El truco aquí es si y > x entonces x^y > y^x con algunas excepciones.
Los siguientes son pasos simples basados en este truco.
- Ordenar array Y[].
- Para cada x en X[], encuentre el índice idx del número más pequeño mayor que x (también llamado techo de x) en Y[] usando la búsqueda binaria, o podemos usar la función incorporada upper_bound() en la biblioteca de algoritmos.
- Todos los números después de idx satisfacen la relación, así que simplemente agregue (n-idx) al conteo.
Casos base y excepciones:
Las siguientes son excepciones para x de X[] e y de Y[]
- Si x = 0, entonces el conteo de pares para esta x es 0.
- Si x = 1, entonces el conteo de pares para este x es igual al conteo de 0s en Y[].
- x menor que y significa que x^y es mayor que y^x.
- x = 2, y = 3 o 4
- x = 3, y = 2
Tenga en cuenta que el caso donde x = 4 y y = 2 no está allí
El siguiente diagrama muestra todas las excepciones en forma tabular. El valor 1 indica que las correspondientes (x, y) forman un par válido.
En la siguiente implementación, preprocesamos la array Y y contamos 0, 1, 2, 3 y 4 en ella, para que podamos manejar todas las excepciones en tiempo constante. La array NoOfY[] se utiliza para almacenar los recuentos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to finds the number of pairs (x, y)
// in an array such that x^y > y^x
#include <bits/stdc++.h>
using namespace std;
// Function to return count of pairs with x as one element
// of the pair. It mainly looks for all values in Y[] where
// x ^ Y[i] > Y[i] ^ x
int count(int x, int Y[], int n, int NoOfY[])
{
// If x is 0, then there cannot be any value in Y such
// that x^Y[i] > Y[i]^x
if (x == 0)
return 0;
// If x is 1, then the number of pairs is equal to number
// of zeroes in Y[]
if (x == 1)
return NoOfY[0];
// Find number of elements in Y[] with values greater
// than x upper_bound() gets address of first greater
// element in Y[0..n-1]
int* idx = upper_bound(Y, Y + n, x);
int ans = (Y + n) - idx;
// If we have reached here, then x must be greater than
// 1, increase number of pairs for y=0 and y=1
ans += (NoOfY[0] + NoOfY[1]);
// Decrease number of pairs for x=2 and (y=4 or y=3)
if (x == 2)
ans -= (NoOfY[3] + NoOfY[4]);
// Increase number of pairs for x=3 and y=2
if (x == 3)
ans += NoOfY[2];
return ans;
}
// Function to return count of pairs (x, y) such that
// x belongs to X[], y belongs to Y[] and x^y > y^x
int countPairs(int X[], int Y[], int m, int n)
{
// To store counts of 0, 1, 2, 3 and 4 in array Y
int NoOfY[5] = { 0 };
for (int i = 0; i < n; i++)
if (Y[i] < 5)
NoOfY[Y[i]]++;
// Sort Y[] so that we can do binary search in it
sort(Y, Y + n);
int total_pairs = 0; // Initialize result
// Take every element of X and count pairs with it
for (int i = 0; i < m; i++)
total_pairs += count(X[i], Y, n, NoOfY);
return total_pairs;
}
// Driver program
int main()
{
int X[] = { 2, 1, 6 };
int Y[] = { 1, 5 };
int m = sizeof(X) / sizeof(X[0]);
int n = sizeof(Y) / sizeof(Y[0]);
cout << "Total pairs = " << countPairs(X, Y, m, n);
return 0;
}
Java
// Java program to finds number of pairs (x, y)
// in an array such that x^y > y^x
import java.util.Arrays;
class Test {
// Function to return count of pairs with x as one
// element of the pair. It mainly looks for all values
// in Y[] where x ^ Y[i] > Y[i] ^ x
static int count(int x, int Y[], int n, int NoOfY[])
{
// If x is 0, then there cannot be any value in Y
// such that x^Y[i] > Y[i]^x
if (x == 0)
return 0;
// If x is 1, then the number of pairs is equal to
// number of zeroes in Y[]
if (x == 1)
return NoOfY[0];
// Find number of elements in Y[] with values
// greater than x getting upperbound of x with
// binary search
int idx = Arrays.binarySearch(Y, x);
int ans;
if (idx < 0) {
idx = Math.abs(idx + 1);
ans = Y.length - idx;
}
else {
while (idx < n && Y[idx] == x) {
idx++;
}
ans = Y.length - idx;
}
// If we have reached here, then x must be greater
// than 1, increase number of pairs for y=0 and y=1
ans += (NoOfY[0] + NoOfY[1]);
// Decrease number of pairs for x=2 and (y=4 or y=3)
if (x == 2)
ans -= (NoOfY[3] + NoOfY[4]);
// Increase number of pairs for x=3 and y=2
if (x == 3)
ans += NoOfY[2];
return ans;
}
// Function to returns count of pairs (x, y) such that
// x belongs to X[], y belongs to Y[] and x^y > y^x
static long countPairs(int X[], int Y[], int m, int n)
{
// To store counts of 0, 1, 2, 3 and 4 in array Y
int NoOfY[] = new int[5];
for (int i = 0; i < n; i++)
if (Y[i] < 5)
NoOfY[Y[i]]++;
// Sort Y[] so that we can do binary search in it
Arrays.sort(Y);
long total_pairs = 0; // Initialize result
// Take every element of X and count pairs with it
for (int i = 0; i < m; i++)
total_pairs += count(X[i], Y, n, NoOfY);
return total_pairs;
}
// Driver method
public static void main(String args[])
{
int X[] = { 2, 1, 6 };
int Y[] = { 1, 5 };
System.out.println(
"Total pairs = "
+ countPairs(X, Y, X.length, Y.length));
}
}
Python3
# Python3 program to find the number
# of pairs (x, y) in an array
# such that x^y > y^x
import bisect
# Function to return count of pairs
# with x as one element of the pair.
# It mainly looks for all values in Y
# where x ^ Y[i] > Y[i] ^ x
def count(x, Y, n, NoOfY):
# If x is 0, then there cannot be
# any value in Y such that
# x^Y[i] > Y[i]^x
if x == 0:
return 0
# If x is 1, then the number of pairs
# is equal to number of zeroes in Y
if x == 1:
return NoOfY[0]
# Find number of elements in Y[] with
# values greater than x, bisect.bisect_right
# gets address of first greater element
# in Y[0..n-1]
idx = bisect.bisect_right(Y, x)
ans = n - idx
# If we have reached here, then x must be greater than 1,
# increase number of pairs for y=0 and y=1
ans += NoOfY[0] + NoOfY[1]
# Decrease number of pairs
# for x=2 and (y=4 or y=3)
if x == 2:
ans -= NoOfY[3] + NoOfY[4]
# Increase number of pairs
# for x=3 and y=2
if x == 3:
ans += NoOfY[2]
return ans
# Function to return count of pairs (x, y)
# such that x belongs to X,
# y belongs to Y and x^y > y^x
def count_pairs(X, Y, m, n):
# To store counts of 0, 1, 2, 3,
# and 4 in array Y
NoOfY = [0] * 5
for i in range(n):
if Y[i] < 5:
NoOfY[Y[i]] += 1
# Sort Y so that we can do binary search in it
Y.sort()
total_pairs = 0 # Initialize result
# Take every element of X and
# count pairs with it
for x in X:
total_pairs += count(x, Y, n, NoOfY)
return total_pairs
# Driver Code
if __name__ == '__main__':
X = [2, 1, 6]
Y = [1, 5]
print("Total pairs = ",
count_pairs(X, Y, len(X), len(Y)))
# This code is contributed by shaswatd673
C#
// C# program to finds number of pairs (x, y)
// in an array such that x^y > y^x
using System;
class GFG {
// Function to return count of pairs
// with x as one element of the pair.
// It mainly looks for all values in Y[]
// where x ^ Y[i] > Y[i] ^ x
static int count(int x, int[] Y, int n, int[] NoOfY)
{
// If x is 0, then there cannot be any
// value in Y such that x^Y[i] > Y[i]^x
if (x == 0)
return 0;
// If x is 1, then the number of pairs
// is equal to number of zeroes in Y[]
if (x == 1)
return NoOfY[0];
// Find number of elements in Y[] with
// values greater than x getting
// upperbound of x with binary search
int idx = Array.BinarySearch(Y, x);
int ans;
if (idx < 0) {
idx = Math.Abs(idx + 1);
ans = Y.Length - idx;
}
else {
while (idx < n && Y[idx] == x) {
idx++;
}
ans = Y.Length - idx;
}
// If we have reached here, then x
// must be greater than 1, increase
// number of pairs for y = 0 and y = 1
ans += (NoOfY[0] + NoOfY[1]);
// Decrease number of pairs
// for x = 2 and (y = 4 or y = 3)
if (x == 2)
ans -= (NoOfY[3] + NoOfY[4]);
// Increase number of pairs for x = 3 and y = 2
if (x == 3)
ans += NoOfY[2];
return ans;
}
// Function to that returns count
// of pairs (x, y) such that x belongs
// to X[], y belongs to Y[] and x^y > y^x
static int countPairs(int[] X, int[] Y, int m, int n)
{
// To store counts of 0, 1, 2, 3 and 4 in array Y
int[] NoOfY = new int[5];
for (int i = 0; i < n; i++)
if (Y[i] < 5)
NoOfY[Y[i]]++;
// Sort Y[] so that we can do binary search in it
Array.Sort(Y);
int total_pairs = 0; // Initialize result
// Take every element of X and count pairs with it
for (int i = 0; i < m; i++)
total_pairs += count(X[i], Y, n, NoOfY);
return total_pairs;
}
// Driver method
public static void Main()
{
int[] X = { 2, 1, 6 };
int[] Y = { 1, 5 };
Console.Write(
"Total pairs = "
+ countPairs(X, Y, X.Length, Y.Length));
}
}
// This code is contributed by Sam007
Javascript
<script>
// JavaScript program to finds number of pairs (x, y)
// in an array such that x^y > y^x
// Iterative function to implement Binary Search
function binarySearch(arr, x) {
let start=0, end=arr.length-1;
// Iterate while start not meets end
while (start<=end){
// Find the mid index
let mid=parseInt((start + end)/2);
// If element is present at mid, return True
if (arr[mid]===x) return mid;
// Else look in left or right half accordingly
else if (arr[mid] < x)
start = mid + 1;
else
end = mid - 1;
}
return -1;
}
// Function to return count of pairs with x as one
// element of the pair. It mainly looks for all values
// in Y where x ^ Y[i] > Y[i] ^ x
function count(x , Y , n , NoOfY) {
// If x is 0, then there cannot be any value in Y
// such that x^Y[i] > Y[i]^x
if (x == 0)
return 0;
// If x is 1, then the number of pairs is equal to
// number of zeroes in Y
if (x == 1)
return NoOfY[0];
// Find number of elements in Y with values
// greater than x getting upperbound of x with
// binary search
var idx = binarySearch(Y, x);
var ans;
if (idx < 0) {
idx = Math.abs(idx + 1);
ans = Y.length - idx;
} else {
while (idx < n && Y[idx] == x) {
idx++;
}
ans = Y.length - idx;
}
// If we have reached here, then x must be greater
// than 1, increase number of pairs for y=0 and y=1
ans += (NoOfY[0] + NoOfY[1]);
// Decrease number of pairs for x=2 and (y=4 or y=3)
if (x == 2)
ans -= (NoOfY[3] + NoOfY[4]);
// Increase number of pairs for x=3 and y=2
if (x == 3)
ans += NoOfY[2];
return ans;
}
// Function to returns count of pairs (x, y) such that
// x belongs to X, y belongs to Y and x^y > y^x
function countPairs(X , Y , m , n) {
// To store counts of 0, 1, 2, 3 and 4 in array Y
var NoOfY = Array(5).fill(-1);
for (var i = 0; i < n; i++)
if (Y[i] < 5)
NoOfY[Y[i]]++;
// Sort Y so that we can do binary search in it
Y.sort((a,b)=>a-b);
var total_pairs = 0; // Initialize result
// Take every element of X and count pairs with it
for (var i = 0; i < m; i++)
total_pairs += count(X[i], Y, n, NoOfY);
return total_pairs;
}
// Driver method
var X = [ 2, 1, 6 ];
var Y = [ 1, 5 ];
document.write("Total pairs = " +
countPairs(X, Y, X.length, Y.length));
// This code contributed by umadevi9616
</script>
Producción
Total pairs = 3
Complejidad de tiempo: O(nLogn + mLogn), donde m y n son los tamaños de las arrays X[] e Y[] respectivamente. El paso de ordenación toma tiempo O(nLogn). Luego, cada elemento de X[] se busca en Y[] mediante la búsqueda binaria. Este paso toma tiempo O(mLogn).
Espacio Auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Shubham Mittal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA