Cuente pares con XOR bit a bit que exceda AND 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 el AND(&) bit a bit de cada par sea menor que su XOR(^) bit a bit .

Ejemplos:

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

Entrada: arr[] = {1, 4, 3, 7, 10}
Salida: 9

Enfoque: el enfoque más simple es atravesar la array y generar todos los pares posibles a partir de la array dada . Para cada par, verifique si su AND(&) bit a bit es menor que el XOR(^) bit a bit de ese par 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.
El recuento total de pares que satisfacen la condición {(X & Y) > (X ^ Y)} son:

$\sum_{i=0}^{31}\binom{bit[i]}{2}$
bit[i] almacena el recuento de elementos de la array cuya posición del bit más significativo (MSB) es i.

Por lo tanto, cuenta total de pares que satisfacen la condición dada{(X & Y) < (X ^ Y)}
= [{N * (N – 1) /2} – {
$\sum_{i=0}^{31}\binom{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 .
Almacene la posición del bit más significativo de cada elemento de la array dada.
Finalmente, evalúe el resultado con la fórmula mencionada anteriormente e imprima el resultado.

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;
    }
    res = (N * (N - 1)) / 2 - res;
 
    return res;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
    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;
    }
    res = (N * (N - 1)) / 2 - res;
 
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 1, 2, 3, 4, 5, 6 };
    int N = arr.length;
     
    System.out.println(cntPairs(arr, N));
}
}
 
// This code is contributed by akhilsaini

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(0, N):
         
        # Stores the index of
        # MSB of array elements
        pos = int(math.log(arr[i], 2))
        bit[pos] = bit[pos] + 1
     
    # Calculate number of pairs
    for i in range(0, 32):
        res = res + int((bit[i] *
                        (bit[i] - 1)) / 2)
                         
    res = int((N * (N - 1)) / 2 - res)
     
    return res
 
# Driver Code
if __name__ == "__main__":
     
    arr = [ 1, 2, 3, 4, 5, 6 ]
    N = len(arr)
     
    print(cntPairs(arr, N))
 
# This code is contributed by akhilsaini

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;
    }
    res = (N * (N - 1)) / 2 - res;
 
    return res;
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 1, 2, 3, 4, 5, 6 };
    int N = arr.Length;
     
    Console.Write(cntPairs(arr, N));
}
}
 
// This code is contributed by akhilsaini

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
    let res = 0;
 
    // Stores the count of array
    // elements having same
    // positions of MSB
    let bit = new Array(32).fill(0);
 
    // Traverse the array
    for(let i = 0; i < N; i++)
    {
     
        // Stores the index of
        // MSB of array elements
        let pos = parseInt(Math.log(arr[i]) /
                           Math.log(2));;
        bit[pos]++;
    }
 
    // Calculate number of pairs
    for(let i = 0; i < 32; i++)
    {
        res += parseInt((bit[i]
                * (bit[i] - 1)) / 2);
    }
    res = parseInt((N * (N - 1)) / 2) - res;
 
    return res;
}
 
// Driver Code
let arr = [ 1, 2, 3, 4, 5, 6 ];
let N = arr.length;
 
document.write(cntPairs(arr, N));
 
// This code is contributed by subhammahato348.
 
</script>

Producción:

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

Método 2: Bitwise y es mayor que bitwise xor si y solo si el bit más significativo es igual.

Cree una array de bits [] de tamaño 32 (número máximo de bits)
Inicializar ans a 0.
Recorreremos la array desde el principio y para cada número,
- Encuentre su bit más significativo y diga que es j.
- Agregue el valor almacenado en la array bits[j] al ans . (para el elemento actual bits[j] se puede formar un número de pares)
- Ahora aumente el valor de bits[j] en 1 .
Ahora número total de pares = n*(n-1)/2 . Resta el ans de él.

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
int findCount(int arr[], int N)
{
    // For storing number of pairs
    int ans = 0;
 
    // For storing count of numbers
    int bits[32] = { 0 };
 
    // Iterate from 0 to N - 1
    for (int i = 0; i < N; i++) {
 
        // Find the most significant bit
        int val = log2l(arr[i]);
 
        ans += bits[val];
        bits[val]++;
    }
    return N * (N - 1) / 2 - ans;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 2, 3, 4, 5, 6 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << findCount(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
static int findCount(int arr[], int N)
{
     
    // For storing number of pairs
    int ans = 0;
 
    // For storing count of numbers
    int bits[] = new int[32];
 
    // Iterate from 0 to N - 1
    for(int i = 0; i < N; i++)
    {
         
        // Find the most significant bit
        int val = (int)(Math.log(arr[i]) /
                        Math.log(2));
 
        ans += bits[val];
        bits[val]++;
    }
    return N * (N - 1) / 2 - ans;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    int arr[] = { 1, 2, 3, 4, 5, 6 };
 
    int N = arr.length;
 
    // Function Call
    System.out.println(findCount(arr, N));
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for the above approach
import math
def findCount(arr, N):
 
    # For storing number of pairs
    ans = 0
 
    # For storing count of numbers
    bits = [0] * 32
 
    # Iterate from 0 to N - 1
    for i in range(N):
 
        # Find the most significant bit
        val = int(math.log2(arr[i]))
 
        ans += bits[val]
        bits[val] += 1
    return (N * (N - 1) // 2 - ans)
 
# Driver Code
if __name__ == "__main__":
 
    # Given array arr[]
    arr = [1, 2, 3, 4, 5, 6]
 
    N = len(arr)
 
    # Function Call
    print(findCount(arr, N))
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
 
class GFG{
 
static int findCount(int[] arr, int N)
{
     
    // For storing number of pairs
    int ans = 0;
 
    // For storing count of numbers
    int[] bits = new int[32];
 
    // Iterate from 0 to N - 1
    for(int i = 0; i < N; i++)
    {
         
        // Find the most significant bit
        int val = (int)(Math.Log(arr[i]) /
                        Math.Log(2));
 
        ans += bits[val];
        bits[val]++;
    }
    return N * (N - 1) / 2 - ans;
}
 
// Driver Code
public static void Main()
{
     
    // Given array arr[]
    int[] arr = { 1, 2, 3, 4, 5, 6 };
 
    int N = arr.Length;
 
    // Function Call
    Console.Write(findCount(arr, N));
}
}
 
// This code is contributed by subhammahato348

Javascript

<script>
 
// Javascript program for the above approach
function findCount(arr, N)
{
     
    // For storing number of pairs
    let ans = 0;
 
    // For storing count of numbers
    let bits = new Array(32).fill(0);
 
    // Iterate from 0 to N - 1
    for(let i = 0; i < N; i++)
    {
         
        // Find the most significant bit
        let val = parseInt(Math.log(arr[i]) /
                           Math.log(2));
 
        ans += bits[val];
        bits[val]++;
    }
    return parseInt(N * (N - 1) / 2) - ans;
}
 
// Driver Code
 
// Given array arr[]
let arr = [ 1, 2, 3, 4, 5, 6 ];
 
let N = arr.length;
 
// Function Call
document.write(findCount(arr, N));
 
// This code is contributed by subhammahato348
 
</script>

Producción

Complejidad de tiempo: O(N)

Complejidad espacial: O(32) = O(1)

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta