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>
Producción:
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