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)