Dada una array arr que contiene N enteros positivos. Encuentre el recuento de todos los pares posibles cuyo valor XOR en bits sea mayor que el valor AND en bits
Ejemplos :
Entrada : arr[]={ 12, 4, 15}
Salida : 2
Explicación : 12 ^ 4 = 8, 12 y 4 = 4. entonces 12 ^ 4 > 12 y 4
4 ^ 15 = 11, 4 y 15 = 4. entonces 4 ^ 15 > 4 y 15 .
Entonces, los dos anteriores son pares válidos { 12,4 } ,{4, 15} .Entrada: arr[] ={ 1, 1, 3, 3 }
Salida: 4
Enfoque ingenuo: Para conocer el enfoque de fuerza bruta para resolver este problema, consulte el SET 1 de este artículo .
Complejidad temporal: O(N*N)
Espacio auxiliar: O(1)
Enfoque eficiente: El enfoque eficiente para resolver este problema se basa en la siguiente observación:
Observación:
La observación es que si el índice de MSB (bit más significativo, también conocido como bit de conjunto más a la izquierda), de dos elementos cualesquiera es el mismo, entonces se garantiza que el XOR bit a bit de esos dos elementos es menor que su AND bit a bit, porque 1^1=0, desactivará el MSB. mientras 1&1=1, MSB permanecerá establecido.
Ilustración:
Si a = 1010, b = 1000,
Entonces a & b= 1000 y a ^ b = 0010
Entonces, si el índice MSB es el mismo en ambos, entonces su XOR bit a bit siempre será menor que AND bit a bit. Viceversa, si el índice MSB es diferente, entonces su valor XOR bit a bit será mayor que el valor AND bit a bit. Considere el siguiente ejemplo para entender esta oración.
Siga los pasos a continuación para resolver este problema:
- Construya una array MSB, MSB[ i ] representará el recuento de los elementos cuyo índice de bit MSB es i.
- Eliminar (MSB[ i ]*(MSB[ i ]-1))/2 del total. Porque el par cuyo MSB es el mismo no es un par válido.
- Devuelve el recuento válido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Count number of pairs
//whose bit wise XOR value is greater
//than bit wise AND value
#include <bits/stdc++.h>
using namespace std;
int MSB[32];
// return count of pairs
// whose bitwise xor >= bitwise
long long valid_pairs(int arr[], int N)
{
for (int i = 0; i < N; i++) {
// index of MSB in arr[i]
int MSB_index = log2(arr[i]);
MSB[MSB_index]++;
}
long long tot = (N * (N - 1)) / 2;
long long invalid = 0;
// pairs are invalid if
// their MSB index are same
for (int i = 0; i < 32; i++)
invalid += ((MSB[i] * 1LL * (MSB[i] - 1)) / 2);
long long valid = tot - invalid;
return valid;
}
//Driver Code
int main()
{
int N = 3;
int arr[] = { 12, 4, 15 };
cout << valid_pairs(arr, N);
}
Java
// Java program to Count number of pairs
// whose bit wise XOR value is greater
// than bit wise AND value
import java.io.*;
import java.lang.*;
class GFG
{
// Function to calculate the
// log base 2 of an integer
public static int log2(int N)
{
// calculate log2 N indirectly
// using log() method
int result = (int)(Math.log(N) / Math.log(2));
return result;
}
static int MSB[] = new int[32];
// return count of pairs
// whose bitwise xor >= bitwise
public static long valid_pairs(int arr[], int N)
{
for (int i = 0; i < N; i++) {
// index of MSB in arr[i]
int MSB_index = log2(arr[i]);
MSB[MSB_index]++;
}
long tot = (N * (N - 1)) / 2;
long invalid = 0;
// pairs are invalid if
// their MSB index are same
for (int i = 0; i < 32; i++)
invalid += (((long)MSB[i] * (MSB[i] - 1)) / 2);
long valid = tot - invalid;
return valid;
}
public static void main(String[] args)
{
int N = 3;
int arr[] = { 12, 4, 15 };
System.out.print(valid_pairs(arr, N));
}
}
// This code is contributed by Rohit Pradhan
Python3
# python3 program to Count number of pairs # whose bit wise XOR value is greater # than bit wise AND value import math MSB = [0 for _ in range(32)] # return count of pairs # whose bitwise xor >= bitwise def valid_pairs(arr, N): for i in range(0, N): # index of MSB in arr[i] MSB_index = int(math.log2(arr[i])) MSB[MSB_index] += 1 tot = (N * (N - 1)) // 2 invalid = 0 # pairs are invalid if # their MSB index are same for i in range(0, 32): invalid += ((MSB[i] * (MSB[i] - 1)) // 2) valid = tot - invalid return valid # Driver Code if __name__ == "__main__": N = 3 arr = [12, 4, 15] print(valid_pairs(arr, N)) # This code is contributed by rakeshsahni
C#
// C# program to Count number of pairs
// whose bit wise XOR value is greater
// than bit wise AND value
using System;
public class GFG{
// Function to calculate the
// log base 2 of an integer
public static int log2(int N)
{
// calculate log2 N indirectly
// using log() method
int result = (int)(Math.Log(N) / Math.Log(2));
return result;
}
static int[] MSB = new int[32];
// return count of pairs
// whose bitwise xor >= bitwise
public static long valid_pairs(int[] arr, int N)
{
for (int i = 0; i < N; i++) {
// index of MSB in arr[i]
int MSB_index = log2(arr[i]);
MSB[MSB_index]++;
}
long tot = (N * (N - 1)) / 2;
long invalid = 0;
// pairs are invalid if
// their MSB index are same
for (int i = 0; i < 32; i++)
invalid += (((long)MSB[i] * (MSB[i] - 1)) / 2);
long valid = tot - invalid;
return valid;
}
static public void Main (){
int N = 3;
int[] arr = { 12, 4, 15 };
Console.Write(valid_pairs(arr, N));
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code for the above approach
let MSB = new Array(32).fill(0);
// return count of pairs
// whose bitwise xor >= bitwise
function valid_pairs(arr, N)
{
for (let i = 0; i < N; i++)
{
// index of MSB in arr[i]
let MSB_index = Math.floor(Math.log2(arr[i]));
MSB[MSB_index]++;
}
let tot = Math.floor((N * (N - 1)) / 2);
let invalid = 0;
// pairs are invalid if
// their MSB index are same
for (let i = 0; i < 32; i++)
invalid += Math.floor(((MSB[i] * 1 * (MSB[i] - 1)) / 2));
let valid = tot - invalid;
return valid;
}
// Driver Code
let N = 3;
let arr = [12, 4, 15]
document.write(valid_pairs(arr, N));
// This code is contributed by Potta Lokesh
</script>
2
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)