Dada una array arr[] y un entero K , la tarea es maximizar el OR bit a bit de la array arr[] , donde cada elemento de arr[] se puede incrementar en casi K .
Ejemplos:
Entrada: arr[]= {1, 3, 7, 0, 6, 1}, K = 2
Salida: [1 3 8 0 6 1]
Explicación: Aumente el número 7 en 1, es decir, 8 después de que o de la array sea máximo que es 15Entrada: arr[] ={2, 4, 7, 9}, K = 2
Salida: [2, 4, 7, 9]
Explicación: El OR bit a bit de arr[] ya es 15, por lo que no se requiere ningún cambio. 15 es el máximo OR posible.
Enfoque: este problema se puede resolver mediante el uso de operaciones bit a bit. Siga los pasos a continuación para resolver el problema dado.
- Encuentre el bit a bit o de todos los elementos, que le indicaría el estado de cada bit.
- Comience desde MSB (bit más significativo) , porque MSB hace muchos cambios en el OR bit a bit final.
- Si el bit particular de bit a bit o no está configurado. Encuentre los pasos mínimos para configurar ese bit.
- Los pasos mínimos para configurar el i-ésimo bit son (1<<i)-((1<<i)-1) & arr[i] .
- Cuente los pasos mínimos y actualice la array si los pasos mínimos son más pequeños que iguales a K .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
void MaximizeBitwiseOR(long a[], int k, int n)
{
// For storing initial
// bitwise OR of array arr[]
long oris = 0;
long bitwiseOr = 0;
for (int i = 0; i < n; ++i)
{
bitwiseOr |= a[i];
}
for (int i = 60; i >= 0; i--)
{
if (((1L << i) & bitwiseOr) == 0)
{
long minSteps = LONG_MAX;
int mini = -1;
for (int j = 0; j < n; j++)
{
long y = ((1L << i) - 1) & a[j];
long steps = (1L << i) - y;
if (steps <= k && steps < minSteps)
{
minSteps = steps;
mini = j;
}
}
if (mini != -1)
{
k -= minSteps;
a[mini] += minSteps;
long orr = 0;
for (int j = 0; j < n; j++)
{
orr |= a[j];
}
bitwiseOr = orr;
}
}
}
// Print the required result
for (long elements = 0; elements < n; elements++)
{
if(a[elements]>0)
cout << a[elements] << " ";
else
cout<<0<<" ";
}
}
// Driver code
int main()
{
int N = 6;
int K = 2;
long arr[] = {1, 3, 7, 0, 6, 1};
MaximizeBitwiseOR(arr, K, N);
}
// This code is contributed by Potta Lokesh
Java
import java.io.*;
class Main {
static void MaximizeBitwiseOR(long[] a, int k, int n)
{
// For storing initial
// bitwise OR of array arr[]
long or = 0;
long bitwiseOr = 0;
for (int i = 0; i < a.length; ++i) {
bitwiseOr |= a[i];
}
for (int i = 60; i >= 0; i--) {
if (((1L << i) & bitwiseOr) == 0) {
long minSteps = Long.MAX_VALUE;
int mini = -1;
for (int j = 0; j < n; j++) {
long y = ((1L << i) - 1) & a[j];
long steps = (1L << i) - y;
if (steps <= k
&& steps < minSteps) {
minSteps = steps;
mini = j;
}
}
if (mini != -1) {
k -= minSteps;
a[mini] += minSteps;
long orr = 0;
for (int j = 0; j < n; j++) {
orr |= a[j];
}
bitwiseOr = orr;
}
}
}
// Print the required result
for (long elements : a) {
System.out.print(elements + " ");
}
}
// Driver code
public static void main(String[] args)
{
int N = 6;
int K = 2;
long arr[] = { 1, 3, 7, 0, 6, 1 };
MaximizeBitwiseOR(arr, K, N);
}
}
Python3
# Python3 code for the above approach import sys def MaximizeBitwiseOR(a, k, n): # For storing initial # bitwise OR of array arr[] oris = 0 bitwiseOr = 0 for i in range(n): bitwiseOr |= a[i] for i in range(60, -1, -1): if (((1 << i) & bitwiseOr) == 0): minSteps = sys.maxsize mini = -1 for j in range(n): y = ((1 << i) - 1) & a[j] steps = (1 << i) - y if (steps <= k and steps < minSteps): minSteps = steps mini = j if (mini != -1): k -= minSteps a[mini] += minSteps orr = 0 for j in range(n): orr |= a[j] bitwiseOr = orr # Print the required result for elements in range(n): if(a[elements] > 0): print(a[elements], end=" ") else: print(0, end=" ") # Driver code if __name__ == "__main__": N = 6 K = 2 arr = [1, 3, 7, 0, 6, 1] MaximizeBitwiseOR(arr, K, N) # This code is contributed by ukasp.
C#
using System;
class GFG {
static void MaximizeBitwiseOR(long[] a, int k, int n)
{
// For storing initial
// bitwise OR of array arr[]
long or = 0;
long bitwiseOr = 0;
for (int i = 0; i < a.Length; ++i) {
bitwiseOr |= a[i];
}
for (int i = 60; i >= 0; i--) {
if (((1L << i) & bitwiseOr) == 0) {
long minSteps = Int32.MaxValue;
int mini = -1;
for (int j = 0; j < n; j++) {
long y = ((1L << i) - 1) & a[j];
long steps = (1L << i) - y;
if (steps <= k
&& steps < minSteps) {
minSteps = steps;
mini = j;
}
}
if (mini != -1) {
k -= (int)minSteps;
a[mini] += minSteps;
long orr = 0;
for (int j = 0; j < n; j++) {
orr |= a[j];
}
bitwiseOr = orr;
}
}
}
// Print the required result
foreach (long elements in a) {
Console.Write(elements + " ");
}
}
// Driver code
public static void Main()
{
int N = 6;
int K = 2;
long []arr = { 1, 3, 7, 0, 6, 1 };
MaximizeBitwiseOR(arr, K, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Producción
1 3 8 0 6 1
Complejidad de Tiempo: O(N*60)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA