Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el tamaño más grande del subconjunto de la array arr[] con AND bit a bit positivo .
Nota: si existe más de uno de estos subconjuntos, devuelva el tamaño de solo un subconjunto.
Ejemplos:
Entrada: arr[] = [7, 13, 8, 2, 3]
Salida: 3
Explicación:
Los subconjuntos que tienen AND bit a bit positivo son {7,13,3} y {7,2,3} son de longitud 3, que es de longitud máxima entre todos los subconjuntos posibles.Entrada: arr[] = [1, 2, 4, 8]
Salida: 1
Enfoque: El problema dado se puede resolver contando el número de bits establecidos en cada posición de bits correspondiente para todos los elementos del arreglo y luego el conteo del máximo de bits establecidos en cualquier posición es el conteo máximo de subconjunto requerido porque el Y bit a bit de todos esos elementos es siempre positivo.
Ilustración :
7 --> 00111
13 --> 01101
8 --> 01000
2 --> 00010
3 --> 00011
------
02233 <-- Evident BitWise AND bit(Most number of 1's in bit grid)
From above it is clearly evident that we can have maximum of 3 bitwise combinations
where combinations are listed below as follows:
{7,13,3}
{7,2,3}
- Inicialice una array, digamos bit[] de tamaño 32 que almacene el recuento de bits establecidos en cada i-ésima posición de bit.
- Recorra la array dada y para cada elemento, diga arr[i] incremente la frecuencia del i-ésimo bit en la array bit[] si el i-ésimo bit está configurado en arr[i] .
- Después de los pasos anteriores, imprima el máximo del bit de array [] para imprimir el tamaño máximo del subconjunto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest possible
// subset having Bitwise AND positive
void largestSubset(int a[], int N)
{
// Stores the number of set bits
// at each bit position
int bit[32] = { 0 };
// Traverse the given array arr[]
for (int i = 0; i < N; i++) {
// Current bit position
int x = 31;
// Loop till array element
// becomes zero
while (a[i] > 0) {
// If the last bit is set
if (a[i] & 1 == 1) {
// Increment frequency
bit[x]++;
}
// Divide array element by 2
a[i] = a[i] >> 1;
// Decrease the bit position
x--;
}
}
// Size of the largest possible subset
cout << *max_element(bit, bit + 32);
}
// Driver Code
int main()
{
int arr[] = { 7, 13, 8, 2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
largestSubset(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
static void largestSubset(int a[], int N)
{
// Stores the number of set bits
// at each bit position
int bit[] = new int[32];
// Traverse the given array arr[]
for (int i = 0; i < N; i++) {
// Current bit position
int x = 31;
// Loop till array element
// becomes zero
while (a[i] > 0) {
// If the last bit is set
if ((int)(a[i] & 1) == (int)1) {
// Increment frequency
bit[x]++;
}
// Divide array element by 2
a[i] = a[i] >> 1;
// Decrease the bit position
x--;
}
}
// Size of the largest possible subset
int max = Integer.MIN_VALUE;
for (int i = 0; i < 32; i++) {
max = Math.max(max, bit[i]);
}
System.out.println(max);
}
// Driver code
public static void main (String[] args)
{
int arr[] = {7, 13, 8, 2, 3};
int N = arr.length;
largestSubset(arr, N);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python 3 program for the above approach # Function to find the largest possible # subset having Bitwise AND positive def largestSubset(a, N): # Stores the number of set bits # at each bit position bit = [0 for i in range(32)] # Traverse the given array arr[] for i in range(N): # Current bit position x = 31 # Loop till array element # becomes zero while(a[i] > 0): # If the last bit is set if (a[i] & 1 == 1): # Increment frequency bit[x] += 1 # Divide array element by 2 a[i] = a[i] >> 1 # Decrease the bit position x -= 1 # Size of the largest possible subset print(max(bit)) # Driver Code if __name__ == '__main__': arr = [7, 13, 8, 2, 3] N = len(arr) largestSubset(arr, N) # This code is contributed by ipg016107.
C#
// C# program for the above approach
using System;
class GFG {
static void largestSubset(int[] a, int N)
{
// Stores the number of set bits
// at each bit position
int[] bit = new int[32];
// Traverse the given array arr[]
for (int i = 0; i < N; i++) {
// Current bit position
int x = 31;
// Loop till array element
// becomes zero
while (a[i] > 0) {
// If the last bit is set
if ((int)(a[i] & 1) == (int)1) {
// Increment frequency
bit[x]++;
}
// Divide array element by 2
a[i] = a[i] >> 1;
// Decrease the bit position
x--;
}
}
// Size of the largest possible subset
int max = Int32.MinValue;
for (int i = 0; i < 32; i++) {
max = Math.Max(max, bit[i]);
}
Console.WriteLine(max);
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 7, 13, 8, 2, 3 };
int N = arr.Length;
largestSubset(arr, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the largest possible
// subset having Bitwise AND positive
function largestSubset(a, N)
{
// Stores the number of set bits
// at each bit position
let bit = new Array(32).fill(0);
// Traverse the given array arr[]
for (let i = 0; i < N; i++) {
// Current bit position
let x = 31;
// Loop till array element
// becomes zero
while (a[i] > 0) {
// If the last bit is set
if (a[i] & 1 == 1) {
// Increment frequency
bit[x]++;
}
// Divide array element by 2
a[i] = a[i] >> 1;
// Decrease the bit position
x--;
}
}
// Size of the largest possible subset
let max = Number.MIN_VALUE;
for (let i = 0; i < 32; i++) {
max = Math.max(max, bit[i]);
}
document.write(max);
}
// Driver Code
let arr = [7, 13, 8, 2, 3];
let N = arr.length;
largestSubset(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad de tiempo: O(N)
- [(32)* (longitud de la array) donde 32 es el tiempo constante, por lo que según el árbol de recurrencia, la complejidad del tiempo es de orden N
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dinijain99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA