Dada una array de números enteros A[] que consta de N números enteros, encuentre el número de triples de índices (i, j, k) tales que A[i] & A[j] & A[k] es 0 (<0 ≤ i , j, k ≤ N y & indica el operador AND bit a bit .
Ejemplos:
Entrada: A[]={2, 1, 3}
Salida: 12
Explicación: Se pueden elegir los siguientes triples i, j, k cuyo AND bit a bit es cero:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1 , k=2) : 2 y 1 y 3
(i=0, j=2, k=1) : 2 y 3 y 1
(i=1, j=0, k=0) : 1 y 2 y 2
( i=1, j=0, k=1) : 1 y 2 y 1
(i=1, j=0, k=2) : 1 y 2 y 3
(i=1, j=1, k=0) : 1 y 1 y 2
(i=1, j=2, k=0) : 1 y 3 y 2
(i=2, j=0, k=1) : 3 y 2 y 1
(i=2, j =1, k=0) : 3 y 1 y 2Entrada: A[]={21, 15, 6}
Salida: 0
Explicación: No existen tales tripletas.
Enfoque: La idea para resolver este problema es usar un Mapa para procesar los elementos de resolución de arreglos. Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa para almacenar frecuencias de todos los valores posibles de A[i] y A[j] . Además, inicialice una respuesta variable con 0 para almacenar el conteo requerido.
- Recorra la array y para cada elemento de la array, recorra el mapa y verifique si cada mapa es clave, si es bit a bit Y con el elemento de la array actual es 0 o no. Para cada elemento de la array para el que se descubra que es cierto, aumente la respuesta por la frecuencia de la clave.
- Después de completar el recorrido de la array, imprima la respuesta .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find the number of // triplets whose Bitwise AND is 0. int countTriplets(vector<int>& A) { // Stores the count of triplets // having bitwise AND equal to 0 int cnt = 0; // Stores frequencies of all possible A[i] & A[j] unordered_map<int, int> tuples; // Traverse the array for (auto a : A) // Update frequency of Bitwise AND // of all array elements with a for (auto b : A) ++tuples[a & b]; // Traverse the array for (auto a : A) // Iterate the map for (auto t : tuples) // If bitwise AND of triplet // is zero, increment cnt if ((t.first & a) == 0) cnt += t.second; // Return the number of triplets // whose Bitwise AND is 0. return cnt; } // Driver Code int main() { // Input Array vector<int> A = { 2, 1, 3 }; // Function Call cout << countTriplets(A); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the number of // triplets whose Bitwise AND is 0. static int countTriplets(int []A) { // Stores the count of triplets // having bitwise AND equal to 0 int cnt = 0; // Stores frequencies of all possible A[i] & A[j] HashMap<Integer,Integer> tuples = new HashMap<Integer,Integer>(); // Traverse the array for (int a : A) // Update frequency of Bitwise AND // of all array elements with a for (int b : A) { if(tuples.containsKey(a & b)) tuples.put(a & b, tuples.get(a & b) + 1); else tuples.put(a & b, 1); } // Traverse the array for (int a : A) // Iterate the map for (Map.Entry<Integer, Integer> t : tuples.entrySet()) // If bitwise AND of triplet // is zero, increment cnt if ((t.getKey() & a) == 0) cnt += t.getValue(); // Return the number of triplets // whose Bitwise AND is 0. return cnt; } // Driver Code public static void main(String[] args) { // Input Array int []A = { 2, 1, 3 }; // Function Call System.out.print(countTriplets(A)); } } // This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to find the number of # triplets whose Bitwise AND is 0. def countTriplets(A) : # Stores the count of triplets # having bitwise AND equal to 0 cnt = 0; # Stores frequencies of all possible A[i] & A[j] tuples = {}; # Traverse the array for a in A: # Update frequency of Bitwise AND # of all array elements with a for b in A: if (a & b) in tuples: tuples[a & b] += 1; else: tuples[a & b] = 1; # Traverse the array for a in A: # Iterate the map for t in tuples: # If bitwise AND of triplet # is zero, increment cnt if ((t & a) == 0): cnt += tuples[t]; # Return the number of triplets # whose Bitwise AND is 0. return cnt; # Driver Code if __name__ == "__main__" : # Input Array A = [ 2, 1, 3 ]; # Function Call print(countTriplets(A)); # This code is contributed by AnkThon
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find the number of // triplets whose Bitwise AND is 0. static int countTriplets(int []A) { // Stores the count of triplets // having bitwise AND equal to 0 int cnt = 0; // Stores frequencies of all possible A[i] & A[j] Dictionary<int,int> tuples = new Dictionary<int,int>(); // Traverse the array foreach (int a in A) // Update frequency of Bitwise AND // of all array elements with a foreach (int b in A) { if(tuples.ContainsKey(a & b)) tuples[a & b] = tuples[a & b] + 1; else tuples.Add(a & b, 1); } // Traverse the array foreach (int a in A) // Iterate the map foreach (KeyValuePair<int, int> t in tuples) // If bitwise AND of triplet // is zero, increment cnt if ((t.Key & a) == 0) cnt += t.Value; // Return the number of triplets // whose Bitwise AND is 0. return cnt; } // Driver Code public static void Main(String[] args) { // Input Array int []A = { 2, 1, 3 }; // Function Call Console.Write(countTriplets(A)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript program for the above approach // Function to find the number of // triplets whose Bitwise AND is 0. function countTriplets(A) { // Stores the count of triplets // having bitwise AND equal to 0 var cnt = 0; // Stores frequencies of all possible A[i] & A[j] var tuples = new Map(); // Traverse the array A.forEach(a => { // Update frequency of Bitwise AND // of all array elements with a A.forEach(b => { if(tuples.has(a & b)) tuples.set(a & b, tuples.get(a & b)+1) else tuples.set(a & b, 1) }); }); // Traverse the array A.forEach(a => { // Update frequency of Bitwise AND // of all array elements with a tuples.forEach((value, key) => { // If bitwise AND of triplet // is zero, increment cnt if ((key & a) == 0) cnt += value; }); }); // Return the number of triplets // whose Bitwise AND is 0. return cnt; } // Driver Code // Input Array var A = [2, 1, 3]; // Function Call document.write( countTriplets(A)); </script>
12
Complejidad de tiempo: O(max(M*N, N 2 )) donde M es el elemento máximo presente en el arreglo dado
Espacio auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA