Cuente los pares cuyo AND bit a bit exceda XOR bit a bit de una array dada

Dada una array arr[] de tamaño N , la tarea es contar el número de pares de la array dada de modo que Bitwise AND (&) de cada par sea mayor que Bitwise XOR(^) .

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4}
Salida: 1
Explicación: Los
pares que satisfacen las condiciones dadas son:
(2 y 3) > (2 ^ 3)
Por lo tanto, la salida requerida es 1.

Entrada: arr[] = { 1, 4, 3, 7}
Salida: 1
Explicación: Los
pares que satisfacen las condiciones dadas son:
(4 y 7) > (4 ^ 7)
Por lo tanto, la salida requerida es 1.

Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array y generar todos los pares posibles a partir de la array dada . Para cada par, verifique si su Bitwise AND ( & ) es mayor que su Bitwise XOR ( ^ ) o no. Si se encuentra que es cierto, entonces incremente el conteo de pares en 1 . Finalmente, imprima el conteo de dichos pares obtenidos.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, siga las propiedades de los operadores bit a bit :

1 ^ 0 = 1
0 ^ 1 = 1
1 & 1 = 1
X = b ₃₁ b ₃₀ …..b ₁ b ₀
Y = a ₃₁ b ₃₀ ….a ₁ a ₀
Si la expresión {(X & Y) > (X ^ Y)} es verdadero, entonces el bit más significativo (MSB) de X e Y debe ser igual.
Recuento total de pares que cumplen la condición {(X & Y) > (X ^ Y)} es igual a:
$\Sigma_{n=0}^{31}(^{bit[i]}_{\ \ \ 2})$

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

Inicializa una variable, digamos res , para almacenar el conteo de pares que satisfacen la condición dada.
Recorre la array dada arr[] .
Almacene las posiciones del bit más significativo ( MSB ) de cada elemento de la array dada.
Inicialice una array de bits [], de tamaño 32 (número máximo de bits)
Iterar sobre cada elemento de la array y realizar los siguientes pasos:
1. Encuentre el bit más significativo ( MSB ) del elemento de array actual, digamos j .
2. Agregue el valor almacenado en bits[j] a la respuesta.
3. Aumente el valor de bits[j] en 1 .

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count pairs that
// satisfy the above condition
int cntPairs(int arr[], int N)
{
 
    // Stores the count of pairs
    int res = 0;
 
    // Stores the count of array
    // elements having same
    // positions of MSB
    int bit[32] = { 0 };
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
        // Stores the index of
        // MSB of array elements
        int pos = log2(arr[i]);
        bit[pos]++;
    }
 
    // Calculate number of pairs
    for (int i = 0; i < 32; i++) {
        res += (bit[i] * (bit[i] - 1)) / 2;
    }
 
    return res;
}
 
// Driver Code
int main()
{
    // Given Input
    int arr[] = { 1, 2, 3, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to count pairs
    // satisfying the given condition
    cout << cntPairs(arr, N);
}

Java

// Java program to implement
// the above approach
import java.io.*;
 
class GFG{
 
// Function to count pairs that
// satisfy the above condition
static int cntPairs(int arr[], int N)
{
 
    // Stores the count of pairs
    int res = 0;
 
    // Stores the count of array
    // elements having same
    // positions of MSB
    int bit[] = new int[32];
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
         
        // Stores the index of
        // MSB of array elements
        int pos = (int)(Math.log(arr[i]) / Math.log(2));
        bit[pos]++;
    }
 
    // Calculate number of pairs
    for(int i = 0; i < 32; i++)
    {
        res += (bit[i] * (bit[i] - 1)) / 2;
    }
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given Input
    int arr[] = { 1, 2, 3, 4 };
    int N = arr.length;
 
    // Function call to count pairs
    // satisfying the given condition
    System.out.println(cntPairs(arr, N));
}
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python3 program to implement
# the above approach
import math
 
# Function to count pairs that
# satisfy the above condition
def cntPairs(arr, N):
 
    # Stores the count of pairs
    res = 0
 
    # Stores the count of array
    # elements having same
    # positions of MSB
    bit = [0] * 32
 
    # Traverse the array
    for i in range(N):
         
        # Stores the index of
        # MSB of array elements
        pos = (int)(math.log2(arr[i]))
        bit[pos] += 1
 
    # Calculate number of pairs
    for i in range(32):
        res += (bit[i] * (bit[i] - 1)) // 2
         
    return res
 
# Driver Code
if __name__ == "__main__":
 
    # Given Input
    arr = [1, 2, 3, 4]
    N = len(arr)
 
    # Function call to count pairs
    # satisfying the given condition
    print(cntPairs(arr, N))
 
# This code is contributed by ukasp

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
     
// Function to count pairs that
// satisfy the above condition
static int cntPairs(int[] arr, int N)
{
 
    // Stores the count of pairs
    int res = 0;
 
    // Stores the count of array
    // elements having same
    // positions of MSB
    int[] bit = new int[32];
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
         
        // Stores the index of
        // MSB of array elements
        int pos = (int)(Math.Log(arr[i]) / Math.Log(2));
        bit[pos]++;
    }
 
    // Calculate number of pairs
    for(int i = 0; i < 32; i++)
    {
        res += (bit[i] * (bit[i] - 1)) / 2;
    }
    return res;
}
 
// Driver Code
static public void Main ()
{
     
    // Given Input
    int[] arr = { 1, 2, 3, 4 };
    int N = arr.Length;
 
    // Function call to count pairs
    // satisfying the given condition
    Console.Write(cntPairs(arr, N));
}
}
 
// This code is contributed by avijitmondal1998

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to count pairs that
// satisfy the above condition
function cntPairs(arr, N)
{
 
    // Stores the count of pairs
    var res = 0;
 
    // Stores the count of array
    // elements having same
    // positions of MSB
    var bit  = Array(32).fill(0);
    var i;
    // Traverse the array
    for( i = 0; i < N; i++) {
        // Stores the index of
        // MSB of array elements
        var pos = Math.ceil(Math.log2(arr[i]));
        bit[pos] += 1;
    }
 
    // Calculate number of pairs
    for (i = 0; i < 32; i++) {
        res += Math.ceil((bit[i] * (bit[i] - 1)) / 2);
    }
 
    return res;
}
 
// Driver Code
    // Given Input
    arr = [1, 2, 3, 4];
    N = arr.length;
 
    // Function call to count pairs
    // satisfying the given condition
    document.write(cntPairs(arr, N));
 
</script>

Producción:

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

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta