Dada una array arr[] de N enteros positivos y un número K , la tarea es encontrar el valor máximo de OR bit a bit de la subsecuencia de tamaño K.
Ejemplos:
Entrada: arr[] = {2, 5, 3, 6, 11, 13}, k = 3
Salida: 15
Explicación:
La subsecuencia tendrá un valor OR máximo de 2, 11, 13.Entrada: arr[] = {5, 9, 7, 19}, k = 3
Salida: 31
Explicación:
El valor máximo de OR bit a bit de la subsecuencia de tamaño K = 3 es 31.
Enfoque ingenuo: el enfoque ingenuo consiste en generar todas las subsecuencias de longitud K y encontrar el valor OR bit a bit de todas las subsecuencias. El máximo entre todos ellos será la respuesta.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(K)
Enfoque eficiente: para optimizar el método anterior, intente implementar el enfoque codicioso . A continuación se muestran los pasos:
- Inicialice una array de enteros bit[] de tamaño 32 con todos los valores iguales a 0.
- Ahora itere para cada índice de la array de bits [] de 31 a 0, y verifique si el i -ésimo valor de la array de bits es 0, luego itere en la array dada y encuentre un elemento que contribuya con un máximo de 1 a nuestra array de bits después de tomarlo.
- Tome ese elemento y cambie la array de bits correspondientemente, también disminuya k cada vez en 1 si k> 0. De lo contrario, salga del ciclo.
- Ahora convierta la array bit[] en un número decimal para obtener la respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to convert bit array to
// decimal number
int build_num(int bit[])
{
int ans = 0;
for (int i = 0; i < 32; i++)
if (bit[i])
ans += (1 << i);
// Return the final result
return ans;
}
// Function to find the maximum Bitwise
// OR value of subsequence of length K
int maximumOR(int arr[], int n, int k)
{
// Initialize bit array of
// size 32 with all value as 0
int bit[32] = { 0 };
// Iterate for each index of bit[]
// array from 31 to 0, and check if
// the ith value of bit array is 0
for (int i = 31; i >= 0; i--) {
if (bit[i] == 0 && k > 0) {
int temp = build_num(bit);
int temp1 = temp;
int val = -1;
for (int j = 0; j < n; j++) {
// Check for maximum
// contributing element
if (temp1 < (temp | arr[j])) {
temp1 = temp | arr[j];
val = arr[j];
}
}
// Update the bit array
// if max_contributing
// element is found
if (val != -1) {
// Decrement the value of K
k--;
for (int j = 0; j < 32; j++) {
if (val & (1 << j))
bit[j]++;
}
}
}
}
// Return the result
return build_num(bit);
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 5, 9, 7, 19 };
// Length of subsequence
int k = 3;
int n = sizeof arr / sizeof arr[0];
// Function Call
cout << maximumOR(arr, n, k);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to convert bit array to
// decimal number
static int build_num(int []bit)
{
int ans = 0;
for(int i = 0; i < 32; i++)
if (bit[i] == 1)
ans += (1 << i);
ans += 32;
// Return the final result
return ans;
}
// Function to find the maximum Bitwise
// OR value of subsequence of length K
static int maximumOR(int []arr, int n, int k)
{
// Initialize bit array of
// size 32 with all value as 0
int bit[] = new int[32];
// Iterate for each index of bit[]
// array from 31 to 0, and check if
// the ith value of bit array is 0
for(int i = 31; i >= 0; i--)
{
if (bit[i] == 0 && k > 0)
{
int temp = build_num(bit);
int temp1 = temp;
int val = -1;
for(int j = 0; j < n; j++)
{
// Check for maximum
// contributing element
if (temp1 < (temp | arr[j]))
{
temp1 = temp | arr[j];
val = arr[j];
}
}
// Update the bit array
// if max_contributing
// element is found
if (val != -1)
{
// Decrement the value of K
k--;
for(int j = 0; j < 32; j++)
{
bit[j]++;
}
}
}
}
// Return the result
return build_num(bit);
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 5, 9, 7, 19 };
// Length of subsequence
int k = 3;
int n = arr.length;
// Function call
System.out.println(maximumOR(arr, n, k));
}
}
// This code is contributed by rock_cool
Python3
# Python3 program to implement # above approach # Function to convert bit array to # decimal number def build_num(bit): ans = 0 for i in range(0, 32): if (bit[i]): ans += (1 << i) # Return the final result return ans; # Function to find the maximum Bitwise # OR value of subsequence of length K def maximumOR(arr, n, k): # Initialize bit array of # size 32 with all value as 0 bit = [0] * 32 # Iterate for each index of bit[] # array from 31 to 0, and check if # the ith value of bit array is 0 for i in range(31, -1, -1): if (bit[i] == 0 and k > 0): temp = build_num(bit) temp1 = temp val = -1 for j in range(0, n): # Check for maximum # contributing element if (temp1 < (temp | arr[j])): temp1 = temp | arr[j] val = arr[j] # Update the bit array # if max_contributing # element is found if (val != -1): # Decrement the value of K k -= 1 for j in range(0, 32): if (val & (1 << j)): bit[j] += 1 # Return the result return build_num(bit) # Driver Code # Given array arr[] arr = [ 5, 9, 7, 19 ] # Length of subsequence k = 3; n = len(arr) # Function call print(maximumOR(arr, n, k)) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG{
// Function to convert bit array to
// decimal number
static int build_num(int []bit)
{
int ans = 0;
for(int i = 0; i < 32; i++)
if (bit[i] == 1)
ans += (1 << i);
ans += 32;
// Return the final result
return ans;
}
// Function to find the maximum Bitwise
// OR value of subsequence of length K
static int maximumOR(int []arr, int n, int k)
{
// Initialize bit array of
// size 32 with all value as 0
int []bit = new int[32];
// Iterate for each index of bit[]
// array from 31 to 0, and check if
// the ith value of bit array is 0
for(int i = 31; i >= 0; i--)
{
if (bit[i] == 0 && k > 0)
{
int temp = build_num(bit);
int temp1 = temp;
int val = -1;
for(int j = 0; j < n; j++)
{
// Check for maximum
// contributing element
if (temp1 < (temp | arr[j]))
{
temp1 = temp | arr[j];
val = arr[j];
}
}
// Update the bit array
// if max_contributing
// element is found
if (val != -1)
{
// Decrement the value of K
k--;
for(int j = 0; j < 32; j++)
{
bit[j]++;
}
}
}
}
// Return the result
return build_num(bit);
}
// Driver Code
public static void Main()
{
// Given array arr[]
int []arr = { 5, 9, 7, 19 };
// Length of subsequence
int k = 3;
int n = arr.Length;
// Function call
Console.Write(maximumOR(arr, n, k));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript program for the above approach
// Function to convert bit array to
// decimal number
function build_num(bit)
{
let ans = 0;
for(let i = 0; i < 32; i++)
if (bit[i] > 0)
ans += (1 << i);
// Return the final result
return ans;
}
// Function to find the maximum Bitwise
// OR value of subsequence of length K
function maximumOR(arr, n, k)
{
// Initialize bit array of
// size 32 with all value as 0
let bit = new Array(32);
bit.fill(0);
// Iterate for each index of bit[]
// array from 31 to 0, and check if
// the ith value of bit array is 0
for(let i = 31; i >= 0; i--)
{
if (bit[i] == 0 && k > 0)
{
let temp = build_num(bit);
let temp1 = temp;
let val = -1;
for(let j = 0; j < n; j++)
{
// Check for maximum
// contributing element
if (temp1 < (temp | arr[j]))
{
temp1 = temp | arr[j];
val = arr[j];
}
}
// Update the bit array
// if max_contributing
// element is found
if (val != -1)
{
// Decrement the value of K
k--;
for(let j = 0; j < 32; j++)
{
if ((val & (1 << j)) > 0)
bit[j]++;
}
}
}
}
// Return the result
return build_num(bit);
}
// Driver code
// Given array arr[]
let arr = [ 5, 9, 7, 19 ];
// Length of subsequence
let k = 3;
let n = arr.length;
// Function Call
document.write(maximumOR(arr, n, k));
// This code is contributed by divyeshrabadiya07
</script>
Producción:
31
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Artículo similar: Valor máximo AND bit a bit de la subsecuencia de longitud K
Publicación traducida automáticamente
Artículo escrito por Stream_Cipher y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA