Dada una array de enteros positivos de tamaño n. Encuentra el conteo de los tripletes cuyo AND es máximo y también encuentra ese máximo dado que i < j < k donde i, j, k son los índices de los números.
Asumiendo que los números no serán mayores que 10^9 .
Ejemplos:
Entrada: a[] = {1, 2, 3, 4, 5, 6}
Salida: 1 4
Explicación: El número máximo que se puede formar es 4 (4, 5 y 6) y solo es posible 1 triplete.
Entrada: a[] = {4, 11, 10, 15, 26}
Salida: 4 10
Explicación: El número máximo que se puede formar es 10. Hay 4 tripletes posibles: {11, 10, 15}, {11, 10, 26}, {11, 15, 26}, {10, 15, 26}
Un enfoque ingenuo es usar 3 bucles y generar todos los tripletes y calcular el número máximo que se puede formar y contar dichos tripletes.
Complejidad de tiempo: O (N ^ 3)
Un mejor enfoque es representar primero el número en su representación binaria y almacenarlo en una array 2d. Dado que el número no puede ser mayor que 2 ^ 32 (debido a las restricciones dadas en la pregunta), tomará un máximo de 32 iteraciones para cada número. También tomaremos una array de bandera booleana que representará qué números se pueden usar para hacer el triplete máximo. Inicialmente establecemos la array en verdadero ya que se pueden usar todos los números.
Deje que el número AND máximo sea X inicialmente cero.
Ahora queremos maximizar X, así que comenzamos a atravesar la tabla 2D desde el índice que representa el bit 32 del número y contaremos el número de 1 que están presentes en el bit 32 de los números que están disponibles para los tripletes, es decir, cuyas banderas son verdaderas. Si el conteo de 1 es mayor que 3, eso significa que hay tripletes posibles para establecer el i-ésimo bit de X, entonces estableceremos la bandera de todos los números cuyo i-ésimo bit no esté establecido y también sumaremos la potencia i a la base 2 a X. De lo contrario, si el conteo es menor que 3, la iésima parte de X se desactivará y no es necesario cambiar las banderas de los números, ya que puede haber combinaciones de 1 y 0 para ese bit.
Repetiremos el proceso anterior para cada bit en orden inverso, desde 32 hasta 0.
En el contaremos el número de números cuyas banderas están configuradas, sea r. Luego, para el número de tripletes, solo necesitamos calcular rC3 { r*(r-1)*(r-2)/6 }.
C++
// CPP program to find triplet with maximum
// bitwise AND.
#include "cmath"
#include "cstring"
#include "iostream"
using namespace std;
int maxTriplet(int a[], int n)
{
// Flag Array initially set to true
// for all numbers
bool f[n];
memset(f, true, sizeof(f));
// 2D array for bit representation
// of all the numbers.
// Initially all bits are set to 0.
int bits[n][33];
memset(bits, 0, sizeof(bits));
for (int i = 0; i < n; ++i) {
int num = a[i];
int j = 32;
// Finding bit representation
// of every number and
// storing it in bits array.
while (num) {
// Checking last bit of the number
if (num & 1) {
bits[i][j] = 1;
}
j--;
// Dividing number by 2.
num >>= 1;
}
}
// maximum And number initially 0.
long long ans = 0;
// Traversing the 2d binary representation.
// 0th index represents 32th bits
// while 32th index represents 0th bit.
for (long long i = 0; i <= 32; ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
if (bits[j][i] and f[j]) {
cnt++;
}
}
// If cnt greater than 3 then (32-i)th bits
// of the number will be set.
if (cnt >= 3) {
ans += pow(2LL, 32 - i);
// Setting flags of the numbers
// whose ith bit is not set.
for (int j = 0; j < n; ++j) {
if (!bits[j][i]) {
f[j] = false;
}
}
}
}
// Counting the numbers whose flag are true.
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (f[i]) {
cnt++;
}
}
long long NumberOfTriplets =
(cnt * (cnt - 1) * (cnt - 2)) / 6;
cout << NumberOfTriplets << " " << ans;
}
int main(int argc, char const* argv[])
{
int a[] = { 4, 11, 10, 15, 26 };
int n = sizeof(a) / sizeof(a[0]);
maxTriplet(a, n);
return 0;
}
Java
// Java program to find triplet with maximum
// bitwise AND.
import java.util.Arrays;
class GFG {
static void maxTriplet(int a[], int n)
{
// Flag Array initially set to true
// for all numbers
boolean []f = new boolean[n];
Arrays.fill(f, true);
// 2D array for bit representation
// of all the numbers.
// Initially all bits are set to 0.
int bits[][] = new int[n][33];
for (int i = 0; i < n; ++i)
{
int num = a[i];
int j = 32;
// Finding bit representation
// of every number and
// storing it in bits array.
while (num > 0)
{
// Checking last bit of the number
if (num % 2 == 1)
{
bits[i][j] = 1;
}
j--;
// Dividing number by 2.
num >>= 1;
}
}
// maximum And number initially 0.
long ans = 0;
// Traversing the 2d binary representation.
// 0th index represents 32th bits
// while 32th index represents 0th bit.
for (int i = 0; i <= 32; ++i)
{
int cnt = 0;
for (int j = 0; j < n; ++j)
{
if (bits[j][i] == 1 & f[j])
{
cnt++;
}
}
// If cnt greater than 3 then (32-i)th bits
// of the number will be set.
if (cnt >= 3) {
ans += Math.pow(2, 32 - i);
// Setting flags of the numbers
// whose ith bit is not set.
for (int j = 0; j < n; ++j) {
if (bits[j][i] != 1) {
f[j] = false;
}
}
}
}
// Counting the numbers whose flag are true.
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (f[i]) {
cnt++;
}
}
long NumberOfTriplets = (cnt * (cnt - 1) * (cnt - 2)) / 6;
System.out.print(NumberOfTriplets + " " + ans);
}
// Driver code
public static void main(String[] args) {
int a[] = { 4, 11, 10, 15, 26 };
int n = a.length;
maxTriplet(a, n);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find triplet with # maximum bitwise AND. def maxTriplet(a, n): # Flag Array initially set to true # for all numbers f = [True for i in range(n)] # 2D array for bit representation # of all the numbers. # Initially all bits are set to 0. bits = [[0 for i in range(33)] for i in range(n)] for i in range(n): num = a[i] j = 32 # Finding bit representation # of every number and # storing it in bits array. while (num): # Checking last bit of the number if (num & 1) : bits[i][j] = 1 j -= 1 # Dividing number by 2. num >>= 1 # maximum And number initially 0. ans = 0 # Traversing the 2d binary representation. # 0th index represents 32th bits # while 32th index represents 0th bit. for i in range(33): cnt = 0 for j in range(n): if (bits[j][i] and f[j]): cnt += 1 # If cnt greater than 3 then (32-i)th # bits of the number will be set. if (cnt >= 3): ans += pow(2, 32 - i) # Setting flags of the numbers # whose ith bit is not set. for j in range(n): if (bits[j][i] == False) : f[j] = False # Counting the numbers whose # flag are true. cnt = 0 for i in range(n): if (f[i]): cnt += 1 NumberOfTriplets = (cnt * (cnt - 1) * (cnt - 2)) // 6 print(NumberOfTriplets, ans) # Driver Code a = [ 4, 11, 10, 15, 26] n = len(a) maxTriplet(a, n) # This code is contributed by Mohit Kumar29
C#
// C# program to find triplet with maximum
// bitwise AND.
using System;
class GFG
{
static void maxTriplet(int []a, int n)
{
// Flag Array initially set to true
// for all numbers
Boolean []f = new Boolean[n];
for (int i = 0; i < n; ++i)
f[i] = true;
// 2D array for bit representation
// of all the numbers.
// Initially all bits are set to 0.
int [,]bits = new int[n, 33];
for (int i = 0; i < n; ++i)
{
int num = a[i];
int j = 32;
// Finding bit representation
// of every number and
// storing it in bits array.
while (num > 0)
{
// Checking last bit of the number
if (num % 2 == 1)
{
bits[i, j] = 1;
}
j--;
// Dividing number by 2.
num >>= 1;
}
}
// maximum And number initially 0.
long ans = 0;
int cnt;
// Traversing the 2d binary representation.
// 0th index represents 32th bits
// while 32th index represents 0th bit.
for (int i = 0; i <= 32; ++i)
{
cnt = 0;
for (int j = 0; j < n; ++j)
{
if (bits[j, i] == 1 & f[j])
{
cnt++;
}
}
// If cnt greater than 3 then (32-i)th bits
// of the number will be set.
if (cnt >= 3)
{
ans += (long)Math.Pow(2, 32 - i);
// Setting flags of the numbers
// whose ith bit is not set.
for (int j = 0; j < n; ++j)
{
if (bits[j, i] != 1)
{
f[j] = false;
}
}
}
}
// Counting the numbers whose flag are true.
cnt = 0;
for (int i = 0; i < n; ++i)
{
if (f[i])
{
cnt++;
}
}
long NumberOfTriplets = (cnt * (cnt - 1) *
(cnt - 2)) / 6;
Console.Write(NumberOfTriplets + " " + ans);
}
// Driver code
public static void Main(String[] args)
{
int []a = { 4, 11, 10, 15, 26 };
int n = a.Length;
maxTriplet(a, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find triplet with maximum
// bitwise AND.
function maxTriplet(a,n)
{
// Flag Array initially set to true
// for all numbers
let f = new Array(n);
for(let i=0;i<n;i++)
{
f[i]=true;
}
// 2D array for bit representation
// of all the numbers.
// Initially all bits are set to 0.
let bits = new Array(n);
for(let i=0;i<n;i++)
{
bits[i]=new Array(33);
for(let j=0;j<33;j++)
{
bits[i][j]=0;
}
}
for (let i = 0; i < n; ++i)
{
let num = a[i];
let j = 32;
// Finding bit representation
// of every number and
// storing it in bits array.
while (num > 0)
{
// Checking last bit of the number
if (num % 2 == 1)
{
bits[i][j] = 1;
}
j--;
// Dividing number by 2.
num >>= 1;
}
}
// maximum And number initially 0.
let ans = 0;
// Traversing the 2d binary representation.
// 0th index represents 32th bits
// while 32th index represents 0th bit.
for (let i = 0; i <= 32; ++i)
{
let cnt = 0;
for (let j = 0; j < n; ++j)
{
if (bits[j][i] == 1 & f[j])
{
cnt++;
}
}
// If cnt greater than 3 then (32-i)th bits
// of the number will be set.
if (cnt >= 3) {
ans += Math.pow(2, 32 - i);
// Setting flags of the numbers
// whose ith bit is not set.
for (let j = 0; j < n; ++j) {
if (bits[j][i] != 1) {
f[j] = false;
}
}
}
}
// Counting the numbers whose flag are true.
let cnt = 0;
for (let i = 0; i < n; ++i) {
if (f[i]) {
cnt++;
}
}
let NumberOfTriplets = (cnt * (cnt - 1) * (cnt - 2)) / 6;
document.write(NumberOfTriplets + " " + ans);
}
// Driver code
let a=[4, 11, 10, 15, 26];
let n = a.length;
maxTriplet(a, n);
// This code is contributed by patel2127
</script>
4 10
Complejidad de tiempo: O (NlogN)
Dado que cada número se puede convertir a su binario en logN.
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA