Dada una array arr[] de tamaño N , la tarea es contar el número de pares cuyo Bitwise XOR es mayor que los dos elementos del par.
Ejemplos:
Entrada: arr[] = {2, 4, 3}
Salida: 2
Explicación: Solo hay 2 pares cuyo Bitwise XOR es mayor que los dos elementos del par:
1) (2, 4): Bitwise XOR = 2 ^ 4 = 6, que es mayor que 2 y 4.
2) (4, 3): Bitwise XOR = 4 ^ 3 = 7, que es mayor que 4 y 3.Entrada: arr[] = {2, 2, 2}
Salida: 0
Explicación: Dado que todos los elementos de la array son iguales, Bitwise XOR de todos los pares posibles es 0. Por lo tanto, no existe tal par
Enfoque : el enfoque más simple es generar todos los pares posibles a partir de la array dada y contar aquellos pares cuyo Bitwise XOR sea mayor que ambos elementos. Imprime el conteo después de verificar todos los pares solo una vez.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that counts the pairs whose
// Bitwise XOR is greater than both
// the elements of pair
void countPairs(int A[], int N)
{
// Stores the count of pairs
int count = 0;
// Generate all possible pairs
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
// Find the Bitwise XOR
int xo = (A[i] ^ A[j]);
// Find the maximum of two
int mx = max(A[i], A[j]);
// If xo < mx, increment count
if (xo > mx) {
count++;
}
}
}
// Print the value of count
cout << count;
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function that counts the pairs whose
// Bitwise XOR is greater than both
// the elements of pair
static void countPairs(int[] A, int N)
{
// Stores the count of pairs
int count = 0;
// Generate all possible pairs
for(int i = 0; i < N; i++)
{
for(int j = i + 1; j < N; j++)
{
// Find the Bitwise XOR
int xo = (A[i] ^ A[j]);
// Find the maximum of two
int mx = Math.max(A[i], A[j]);
// If xo < mx, increment count
if (xo > mx)
{
count++;
}
}
}
// Print the value of count
System.out.println(count);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 4, 3 };
int N = arr.length;
// Function Call
countPairs(arr, N);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach # Function that counts the pairs whose # Bitwise XOR is greater than both # the elements of pair def countPairs(A, N): # Stores the count of pairs count = 0 # Generate all possible pairs for i in range(0, N): for j in range(i + 1, N): # Find the Bitwise XOR xo = (A[i] ^ A[j]) # Find the maximum of two mx = max(A[i], A[j]) # If xo < mx, increment count if (xo > mx): count += 1 # Print the value of count print(count) # Driver Code if __name__ == '__main__': arr = [ 2, 4, 3 ] N = len(arr) # Function Call countPairs(arr, N) # This code is contributed by akhilsaini
C#
// C# program for the above approach
using System;
class GFG{
// Function that counts the pairs whose
// Bitwise XOR is greater than both
// the elements of pair
static void countPairs(int[] A, int N)
{
// Stores the count of pairs
int count = 0;
// Generate all possible pairs
for(int i = 0; i < N; i++)
{
for(int j = i + 1; j < N; j++)
{
// Find the Bitwise XOR
int xo = (A[i] ^ A[j]);
// Find the maximum of two
int mx = Math.Max(A[i], A[j]);
// If xo < mx, increment count
if (xo > mx)
{
count++;
}
}
}
// Print the value of count
Console.WriteLine(count);
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 4, 3 };
int N = arr.Length;
// Function Call
countPairs(arr, N);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// javascript program for the above approach
// Function that counts the pairs whose
// Bitwise XOR is greater than both
// the elements of pair
function countPairs(A , N) {
// Stores the count of pairs
var count = 0;
// Generate all possible pairs
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
// Find the Bitwise XOR
var xo = (A[i] ^ A[j]);
// Find the maximum of two
var mx = Math.max(A[i], A[j]);
// If xo < mx, increment count
if (xo > mx) {
count++;
}
}
}
// Print the value of count
document.write(count);
}
// Driver Code
var arr = [ 2, 4, 3 ];
var N = arr.length;
// Function Call
countPairs(arr, N);
// This code contributed by Rajput-Ji
</script>
Producción:
2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la manipulación de bits . Considere X = A^B y A < B y sea K el bit más significativo del número A. Ahora, si X es mayor que el elemento A y B si y solo si el K -ésimo bit de B es 0 . Si el K -ésimo bit de un entero ya es 0 , entonces cuente los números de manera que el K -ésimo bit sea el bit MSBdel otro entero. A continuación se muestran los pasos:
- Inicialice un conteo de variables para almacenar el conteo de pares y una array, digamos bits [] de tamaño 32 y ordene la array dada .
- Recorra la array y haga lo siguiente:
- Si el elemento actual es 0 , busque el siguiente elemento.
- De lo contrario, recorra todos los bits del elemento actual y, si se establece algún bit en la posición j , incremente el conteo en bits[j] .
- Después de los pasos anteriores, actualice los bits [log 2 (elemento actual)] por 1 .
- Después de los pasos anteriores, imprima el valor de la cuenta como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count pairs whose XOR
// is greater than the pair itself
void countPairs(int A[], int N)
{
// Stores the count of pairs
int count = 0;
// Sort the array
sort(A, A + N);
int bits[32] = { 0 };
// Traverse the array
for (int i = 0; i < N; i++) {
// If current element is 0,
// then ignore it
if (A[i] == 0) {
continue;
}
// Traverse all the bits of
// element A[i]
for (int j = 0; j < 32; j++) {
// If current bit is set
// then update the count
if (!((1LL << j) & A[i])) {
count += bits[j];
}
}
// Update bits[] at the most
// significant bit of A[i]
++bits[(int)(log2l(A[i]))];
}
// Print the count
cout << count;
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to count pairs whose XOR
// is greater than the pair itself
static void countPairs(int[] A, int N)
{
// Stores the count of pairs
int count = 0;
// Sort the array
Arrays.sort(A);
int[] bits = new int[32];
// Traverse the array
for(int i = 0; i < N; i++)
{
// If current element is 0,
// then ignore it
if (A[i] == 0)
{
continue;
}
// Traverse all the bits of
// element A[i]
for(int j = 0; j < 32; j++)
{
// If current bit is set
// then update the count
if (((1 << j) & A[i]) == 0)
{
count += bits[j];
}
}
// Update bits[] at the most
// significant bit of A[i]
++bits[(int)((int)(Math.log(A[i]) /
Math.log(2)))];
}
// Print the count
System.out.println(count);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 4, 3 };
int N = arr.length;
// Function Call
countPairs(arr, N);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach import math # Function to count pairs whose XOR # is greater than the pair itself def countPairs(A, N): # Stores the count of pairs count = 0 # Sort the array A.sort() bits = [0] * 32 # Traverse the array for i in range(0, N): # If current element is 0, # then ignore it if (A[i] == 0): continue # Traverse all the bits of # element A[i] for j in range(0, 32): # If current bit is set # then update the count if (((1 << j) & A[i]) == 0): count += bits[j] # Update bits[] at the most # significant bit of A[i] bits[(int)(math.log(A[i], 2))] += 1 # Print the count print(count) # Driver Code if __name__ == '__main__': arr = [ 2, 4, 3 ] N = len(arr) # Function Call countPairs(arr, N) # This code is contributed by akhilsaini
C#
// C# program for the above approach
using System;
class GFG{
// Function to count pairs whose XOR
// is greater than the pair itself
static void countPairs(int[] A, int N)
{
// Stores the count of pairs
int count = 0;
// Sort the array
Array.Sort(A);
int[] bits = new int[32];
// Traverse the array
for(int i = 0; i < N; i++)
{
// If current element is 0,
// then ignore it
if (A[i] == 0)
{
continue;
}
// Traverse all the bits of
// element A[i]
for(int j = 0; j < 32; j++)
{
// If current bit is set
// then update the count
if (((1 << j) & A[i]) == 0)
{
count += bits[j];
}
}
// Update bits[] at the most
// significant bit of A[i]
++bits[(int)((int)(Math.Log(A[i]) /
Math.Log(2)))];
}
// Print the count
Console.WriteLine(count);
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 4, 3 };
int N = arr.Length;
// Function Call
countPairs(arr, N);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// javascript program for the above approach
// Function to count pairs whose XOR
// is greater than the pair itself
function countPairs(A , N) {
// Stores the count of pairs
var count = 0;
// Sort the array
A.sort();
var bits = Array(32).fill(0);
// Traverse the array
for (i = 0; i < N; i++) {
// If current element is 0,
// then ignore it
if (A[i] == 0) {
continue;
}
// Traverse all the bits of
// element A[i]
for (j = 0; j < 32; j++) {
// If current bit is set
// then update the count
if (((1 << j) & A[i]) == 0) {
count += bits[j];
}
}
// Update bits at the most
// significant bit of A[i]
bits[parseInt(Math.log(A[i]) / Math.log(2))]++;
}
// Print the count
document.write(count);
}
// Driver Code
var arr = [ 2, 4, 3 ];
var N = arr.length;
// Function Call
countPairs(arr, N);
// This code is contributed by Rajput-Ji.
</script>
Producción:
2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA