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