Encuentre el número de pares (x, y) en una array tal que x^y > y^x | conjunto 2

Posted on by Rudeus Greyrat

Dadas dos arrays X[] e Y[] de enteros positivos, encuentre el 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:

Entrada: X[] = {2, 1, 6}, Y = {1, 5} 
Salida: 3 
Explicación: 
Los 3 pares posibles son: 
(2, 1) => 2 1 > 1 2 
(2, 5) = > 2 5 (= 32) > 5 2 (= 25) 
(6, 1) => 6 1 > 1 6
Entrada: X[] = {10, 19, 18}, Y[] = {11, 15, 9 } 
Salida: 2 
Explicación: 
Los pares posibles son (10, 11) y (10, 15).

Para el enfoque ingenuo [O(M*N)] y [O(N logN + M logN)], consulte el conjunto 1 de este artículo .
Enfoque eficiente: los dos enfoques anteriores se pueden optimizar aún más en la complejidad de tiempo O(N) .
Este enfoque utiliza el concepto de suma de sufijos para encontrar la solución. Podemos observar que si y > x, entonces x^y > y^x. Sin embargo, se deben considerar los siguientes casos base y excepciones:

  • Si x = 0, entonces el recuento de posibles y es 0.
  • Si x = 1, entonces el conteo de posibles y es la frecuencia de 0, y la Y[] es la respuesta requerida.
  • Si x = 2, 2 3 < 3 2 y 2 4 = 4 2 . Por tanto, para x = 2, no podemos tener un par válido con y = {2, 3, 4}. Por lo tanto, la suma de las frecuencias de 0, 1 y todos los números gt 4 en Y[] nos da el conteo de pares válidos requeridos
  • Si x = 3, la suma de todas las frecuencias excepto 3 en Y[] nos da el conteo requerido de posibles pares.

Siga los pasos a continuación para resolver el problema:

  • Almacene las frecuencias de cada elemento de la array Y.
  • Almacene la suma de sufijos de la array que contiene las frecuencias.
  • Para cada elemento x en X[] que no pertenezca a ninguno de los casos base, el número posible de y’s será sufijo[x+1] + conteo de 0’s en Y[] + conteo de 1’s en Y[]. Para los casos base, calcule los pares en consecuencia como se discutió anteriormente.
  • Imprime el conteo total de pares.

A continuación se muestra la implementación del enfoque anterior:

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 pairs
int 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 Program
int 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^x
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;
     
    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 pairs
def 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 code
if __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^x
using 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 pairs
function 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>
Producción: 

2

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por vishalkhatana y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *