Dada una array , arr[] de tamaño N , la tarea es contar el número de pares no ordenados de modo que Bitwise AND y Bitwise OR de cada par sean iguales.
Ejemplos:
Entrada: arr[] = {1, 2, 1}
Salida: 1
Explicación:
valor AND bit a bit y valor OR bit a bit todos los pares posibles son:
AND bit a bit del par (arr[0], arr[1]) es (arr[ 0] & arr[1]) = (1 & 2) = 0
AND bit a bit del par (arr[0], arr[1]) es (arr[0] | arr[1]) = (1 | 2) = 3
AND bit a bit del par(arr[0], arr[2]) es (arr[0] & arr[2]) = (1 & 2) = 1
AND bit a bit del par(arr[0], arr [1]) es (arr[0] | arr[1]) = (1 | 2) = 1
AND bit a bit del par (arr[1], arr[2]) es (arr[1] & arr[2 ]) = (2 & 1) = 0
AND bit a bit del par (arr[0], arr[1]) es arr[0] | arr[1] = (2 | 1) = 3
Por lo tanto, la salida requerida es 1.Entrada: arr[] = {1, 2, 3, 1, 2, 2}
Salida: 4
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array y generar todos los pares posibles de la array dada . Para cada par, verifique si Bitwise And del par es igual a Bitwise OR de ese par o no. Si se encuentra que es cierto, entonces incremente el contador. Finalmente, imprima el valor del contador.
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
0 y 0 = 0 y 0 | 0 = 0
0 y 1 = 0 y 0 | 1 = 1
1 y 0 = 0 y 1 | 0 = 1
1 y 1 = 1 y 1 | 1 = 1
Por lo tanto, si ambos elementos de un par son iguales, solo entonces, AND(&) bit a bit y OR(|) bit a bit del par se vuelven iguales.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntPairs para almacenar el recuento de pares cuyo valor Bitwise AND(&) y Bitwise OR(|) es igual.
- Cree un mapa, digamos mp para almacenar la frecuencia de todos los elementos distintos de la array dada.
- Recorre la array dada y almacena la frecuencia de todos los elementos distintos de la array dada en mp .
- Recorra el mapa y verifique si la frecuencia, digamos que la frecuencia es mayor que 1 , luego actualice cntPairs += (freq * (freq – 1)) / 2 .
- Finalmente, imprima el valor de cntPairs.
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 in an array // whose bitwise AND equal to bitwise OR int countPairs(int arr[], int N) { // Store count of pairs whose // bitwise AND equal to bitwise OR int cntPairs = 0; // Stores frequency of // distinct elements of array map<int, int> mp; // Traverse the array for (int i = 0; i < N; i++) { // Increment the frequency // of arr[i] mp[arr[i]]++; } // Traverse map for (auto freq: mp) { cntPairs += (freq.second * (freq.second - 1)) / 2; } return cntPairs; } // Driver Code int main() { int arr[] = { 1, 2, 3, 1, 2, 2 }; int N = sizeof(arr) / sizeof(arr[0]); cout<<countPairs(arr, N); }
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ // Function to count pairs in an array // whose bitwise AND equal to bitwise OR static int countPairs(int[] arr, int N) { // Store count of pairs whose // bitwise AND equal to bitwise OR int cntPairs = 0; // Stores frequency of // distinct elements of array HashMap<Integer, Integer> mp = new HashMap<>(); // Traverse the array for(int i = 0; i < N; i++) { // Increment the frequency // of arr[i] mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1); } // Traverse map for(Map.Entry<Integer, Integer> freq : mp.entrySet()) { cntPairs += (freq.getValue() * (freq.getValue() - 1)) / 2; } return cntPairs; } // Driver Code public static void main(String[] args) { int[] arr = { 1, 2, 3, 1, 2, 2 }; int N = arr.length; System.out.println(countPairs(arr, N)); } } // This code is contributed by akhilsaini
Python3
# Python3 program to implement # the above approach # Function to count pairs in an array # whose bitwise AND equal to bitwise OR def countPairs(arr, N): # Store count of pairs whose # bitwise AND equal to bitwise OR cntPairs = 0 # Stores frequency of # distinct elements of array mp = {} # Traverse the array for i in range(0, N): # Increment the frequency # of arr[i] if arr[i] in mp: mp[arr[i]] = mp[arr[i]] + 1 else: mp[arr[i]] = 1 # Traverse map for freq in mp: cntPairs += int((mp[freq] * (mp[freq] - 1)) / 2) return cntPairs # Driver Code if __name__ == "__main__": arr = [ 1, 2, 3, 1, 2, 2 ] N = len(arr) print(countPairs(arr, N)) # This code is contributed by akhilsaini
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to count pairs in an array // whose bitwise AND equal to bitwise OR static int countPairs(int[] arr, int N) { // Store count of pairs whose // bitwise AND equal to bitwise OR int cntPairs = 0; // Stores frequency of // distinct elements of array Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array for(int i = 0; i < N; i++) { // Increment the frequency // of arr[i] if (!mp.ContainsKey(arr[i])) mp.Add(arr[i], 1); else mp[arr[i]] = mp[arr[i]] + 1; } // Traverse map foreach(KeyValuePair<int, int> freq in mp) { cntPairs += (freq.Value * (freq.Value - 1)) / 2; } return cntPairs; } // Driver Code public static void Main() { int[] arr = { 1, 2, 3, 1, 2, 2 }; int N = arr.Length; Console.WriteLine(countPairs(arr, N)); } } // This code is contributed by akhilsaini
Javascript
<script> // JavaScript program to implement // the above approach // Function to count pairs in an array // whose bitwise AND equal to bitwise OR function countPairs(arr, N) { // Store count of pairs whose // bitwise AND equal to bitwise OR var cntPairs = 0; // Stores frequency of // distinct elements of array var mp = new Map(); // Traverse the array for (var i = 0; i < N; i++) { // Increment the frequency // of arr[i] if(mp.has(arr[i])) mp.set(arr[i], mp.get(arr[i])+1) else mp.set(arr[i], 1); } // Traverse map mp.forEach((value, key) => { cntPairs += parseInt((value * (value - 1)) / 2); }); return cntPairs; } // Driver Code var arr = [1, 2, 3, 1, 2, 2 ]; var N = arr.length; document.write( countPairs(arr, N)); </script>
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sujitmeshram y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA