Dada una array de enteros no negativos y un entero k, encuentre el subconjunto de longitud máxima con OR bit a bit igual a k.
Ejemplos:
Input : arr[] = [1, 4, 2]
k = 3
Output : [1, 2]
Explanation: The bitwise OR of
1 and 2 equals 3. It is not possible to obtain
a subset of length greater than 2.
Input : arr[] = [1, 2, 5]
k = 4
Output : []
No subset's bitwise OR equals 4.
Método 1 (simple):
el método ingenuo sería considerar todos los subconjuntos. Al considerar un subconjunto, calcule su OR bit a bit. Si es igual a k, compare la longitud del subconjunto con la longitud máxima hasta el momento y actualice la longitud máxima si es necesario.
Método 2 (Eficiente):
0 O 0 = 0
1 O 0 = 1
1 O 1 = 1
Por lo tanto, para todas las posiciones en la representación binaria de k con el bit igual a 0, la posición correspondiente en las representaciones binarias de todos los elementos en el subconjunto resultante necesariamente debe ser 0.
Por otro lado, para posiciones en k con el bit igual a 1, tiene que haber al menos un elemento con un 1 en la posición correspondiente. El resto de los elementos pueden tener 0 o 1 en esa posición. No importa.
Por lo tanto, para obtener el subconjunto resultante, recorra la array inicial. Mientras decide si el elemento debe estar en el subconjunto resultante o no, verifique si hay alguna posición en la representación binaria de k que sea 0 y la posición correspondiente en ese elemento sea 1. Si existe tal posición, entonces ignore ese elemento , de lo contrario, inclúyalo en el subconjunto resultante.
¿Cómo determinar si existe una posición en la representación binaria de k que es 0 y la posición correspondiente en un elemento es 1?
Simplemente tome el OR bit a bit de k y ese elemento. Si no es igual a k, entonces existe tal posición y el elemento debe ignorarse. Si su OR bit a bit es igual a k, incluya el elemento actual en el subconjunto resultante.
El paso final es determinar si hay al menos un elemento con un 1 en una posición con 1 en la posición correspondiente en k.
Simplemente calcule el OR bit a bit del subconjunto resultante. Si es igual a k, entonces esta es la respuesta final. De lo contrario, no existe ningún subconjunto que satisfaga la condición.
C++
// CPP Program to find the maximum subset
// with bitwise OR equal to k
#include <bits/stdc++.h>
using namespace std;
// function to find the maximum subset with
// bitwise OR equal to k
void subsetBitwiseORk(int arr[], int n, int k)
{
vector<int> v;
for (int i = 0; i < n; i++) {
// If the bitwise OR of k and element
// is equal to k, then include that element
// in the subset
if ((arr[i] | k) == k)
v.push_back(arr[i]);
}
// Store the bitwise OR of elements in v
int ans = 0;
for (int i = 0; i < v.size(); i++)
ans |= v[i];
// If ans is not equal to k, subset doesn't exist
if (ans != k) {
cout << "Subset does not exist" << endl;
return;
}
for (int i = 0; i < v.size(); i++)
cout << v[i] << ' ';
}
// Driver Code
int main()
{
int k = 3;
int arr[] = { 1, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
subsetBitwiseORk(arr, n, k);
return 0;
}
Java
// Java Program to find the maximum subset
// with bitwise OR equal to k
import java.util.*;
class GFG {
// function to find the maximum subset
// with bitwise OR equal to k
static void subsetBitwiseORk(int arr[],
int n, int k)
{
ArrayList<Integer> v =
new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
// If the bitwise OR of k and
// element is equal to k, then
// include that element in the
// subset
if ((arr[i] | k) == k){
v.add(arr[i]);
}
}
// Store the bitwise OR of elements
// in v
int ans = 0;
for (int i = 0; i < v.size(); i++)
ans = ans|v.get(i);
// If ans is not equal to k, subset
// doesn't exist
if (ans != k) {
System.out.println("Subset does"
+ " not exist" );
return;
}
for (int i = 0; i < v.size(); i++)
System.out.print(v.get(i) + " " );
}
// main function
public static void main(String[] args)
{
int k = 3;
int arr[] = { 1, 4, 2 };
int n = arr.length;
subsetBitwiseORk(arr, n, k);
}
}
// This code is contributed by Arnab Kundu.
Python3
# Python3 Program to find the
# maximum subset with bitwise
# OR equal to k
# function to find the maximum
# subset with bitwise OR equal to k
def subsetBitwiseORk(arr, n, k) :
v = []
for i in range(0, n) :
# If the bitwise OR of k
# and element is equal to k,
# then include that element
# in the subset
if ((arr[i] | k) == k) :
v.append(arr[i])
# Store the bitwise OR
# of elements in v
ans = 0
for i in range(0, len(v)) :
ans |= v[i]
# If ans is not equal to
# k, subset doesn't exist
if (ans != k) :
print ("Subset does not exist\n")
return
for i in range(0, len(v)) :
print ("{} ".format(v[i]), end="")
# Driver Code
k = 3
arr = [1, 4, 2]
n = len(arr)
subsetBitwiseORk(arr, n, k)
# This code is contributed by
# Manish Shaw(manishshaw1)
C#
// C# Program to find the maximum subset
// with bitwise OR equal to k
using System;
using System.Collections;
class GFG {
// function to find the maximum subset
// with bitwise OR equal to k
static void subsetBitwiseORk(int []arr,
int n, int k)
{
ArrayList v = new ArrayList();
for (int i = 0; i < n; i++) {
// If the bitwise OR of k and
// element is equal to k, then
// include that element in the
// subset
if ((arr[i] | k) == k){
v.Add(arr[i]);
}
}
// Store the bitwise OR of
// elements in v
int ans = 0;
for (int i = 0; i < v.Count; i++)
ans = ans|(int)v[i];
// If ans is not equal to k, subset
// doesn't exist
if (ans != k) {
Console.WriteLine("Subset does"
+ " not exist" );
return;
}
for (int i = 0; i < v.Count; i++)
Console.Write((int)v[i] + " " );
}
// main function
static public void Main(String []args)
{
int k = 3;
int []arr = { 1, 4, 2 };
int n = arr.Length;
subsetBitwiseORk(arr, n, k);
}
}
// This code is contributed by Arnab Kundu
PHP
<?php
// PHP Program to find the
// maximum subset with bitwise
// OR equal to k
// function to find the maximum
// subset with bitwise OR equal to k
function subsetBitwiseORk($arr, $n, $k)
{
$v = array();
for ($i = 0; $i < $n; $i++)
{
// If the bitwise OR of k
// and element is equal to k,
// then include that element
// in the subset
if (($arr[$i] | $k) == $k)
array_push($v, $arr[$i]);
}
// Store the bitwise OR
// of elements in v
$ans = 0;
for ($i = 0; $i < count($v); $i++)
$ans |= $v[$i];
// If ans is not equal to
// k, subset doesn't exist
if ($ans != $k)
{
echo ("Subset does not exist\n");
return;
}
for ($i = 0; $i < count($v); $i++)
echo ($v[$i]." ");
}
// Driver Code
$k = 3;
$arr = array(1, 4, 2);
$n = count($arr);
subsetBitwiseORk($arr, $n, $k);
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript Program to find the maximum subset
// with bitwise OR equal to k
// function to find the maximum subset with
// bitwise OR equal to k
function subsetBitwiseORk(arr, n, k)
{
var v = [];
for (var i = 0; i < n; i++) {
// If the bitwise OR of k and element
// is equal to k, then include that element
// in the subset
if ((arr[i] | k) == k)
v.push(arr[i]);
}
// Store the bitwise OR of elements in v
var ans = 0;
for (var i = 0; i < v.length; i++)
ans |= v[i];
// If ans is not equal to k, subset doesn't exist
if (ans != k) {
document.write( "Subset does not exist" );
return;
}
for (var i = 0; i < v.length; i++)
document.write( v[i] + ' ');
}
// Driver Code
var k = 3;
var arr = [1, 4, 2];
var n = arr.length;
subsetBitwiseORk(arr, n, k);
</script>
Producción :
1 2
Complejidad temporal: O(N), donde N es el tamaño de la array.
Publicación traducida automáticamente
Artículo escrito por aganjali10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA