Dado un número entero N que se puede representar en 32 bits, la tarea es encontrar otro número entero X que tenga como máximo K bits configurados en su representación binaria y AND bit a bit de X y N sea máximo.
Ejemplos:
Entrada: N = 5, K = 1
Salida: X = 2
Explicación:
La representación binaria de 5 es 101, el valor posible de X tal que maximiza AND es 2
5 -> 101
2 -> 100
AND suma -> 100 ( 2)
4 es la suma AND máxima que podemos obtener con N y X.Entrada: N = 10, K = 2
Salida: X = 10
Explicación:
La representación binaria de 10 es 1010, X = 10 entero posible al máximo dado Y suma con N con al menos 2 bits establecidos.
10 -> 1010
10 -> 1010
AND suma -> 1010 (10)
10 es la suma AND máxima que podemos obtener con N y X.
Enfoque ingenuo: una solución ingenua es ejecutar un ciclo de 1 a N y tomar AND bit a bit con N, y también verificar si el número de bits establecidos es menor o igual a K. Durante cada iteración, mantenga el valor máximo de AND bit a bit.
Complejidad de tiempo: O(N)
Enfoque eficiente: este problema se puede resolver de manera eficiente utilizando un enfoque codicioso en bits . Dado que N puede tener como máximo 32 bits. Entonces, comenzaremos a atravesar desde el bit más significativo y verificaremos si está configurado (o 1) en N, si no está configurado, no hay necesidad de configurar este bit porque la operación AND lo hará cero en la respuesta final, de lo contrario lo estableceremos en nuestra respuesta requerida. Además, mantendremos el conteo de bits establecidos en cada iteración y verificaremos si no excede K.
Complejidad de tiempo: O(32)
A continuación se muestra la implementación del enfoque eficiente anterior:
C++
// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find
// the integer with
// maximum bitwise with N
int find_max(int n, int k)
{
// Store answer in the bitset
// Initialized with 0
bitset<32> X(0);
// To maintain the count
// of set bits that should
// exceed k
int cnt = 0;
// Start traversing from the
// Most significantif that bit
// is set in n then we will set
// in our answer i.e in X
for (int i = 31; i >= 0 &&
cnt != k; i--)
{
// Checking if the ith bit
// is set in n or not
if (n & (1 << i))
{
X[i] = 1;
cnt++;
}
}
// Converting into integer
return X.to_ulong();
}
// Driver Code
int main()
{
int n = 10, k = 2;
// Function Call
cout << find_max(n, k) <<
endl;
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to find
// the integer with
// maximum bitwise with N
static int find_max(int n,
int k)
{
// Store answer in the
// bitset Initialized
// with 0
int[] X = new int[32];
// To maintain the count
// of set bits that should
// exceed k
int cnt = 0;
// Start traversing from the
// Most significant if that bit
// is set in n then we will set
// in our answer i.e in X
for (int i = 31; i >= 0 &&
cnt != k; i--)
{
// Checking if the ith bit
// is set in n or not
if ((n & (1 << i)) != 0)
{
X[i] = 1;
cnt++;
}
}
String s = "";
for(int i = 31; i >= 0; i--)
s += X[i] == 0 ? '0' : '1';
// Converting into integer
return Integer.parseInt(s,2);
}
// Driver function
public static void main (String[] args)
{
int n = 10, k = 2;
// Function Call
System.out.println(find_max(n, k));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to find the integer with # maximum bitwise with N def find_max(n, k): # Store answer in the # bitset Initialized # with 0 X = [0] * 32 # To maintain the count # of set bits that should # exceed k cnt = 0 # Start traversing from the # Most significant if that bit # is set in n then we will set # in our answer i.e in X i = 31 while (i >= 0 and cnt != k): # Checking if the ith bit # is set in n or not if ((n & (1 << i)) != 0): X[i] = 1 cnt += 1 i -= 1 s = "" for i in range(31, -1, -1): if X[i] == 0: s += '0' else: s += '1' # Converting into integer return int(s, 2) # Driver code n, k = 10, 2 # Function Call print(find_max(n, k)) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the integer with
// maximum bitwise with N
static int find_max(int n, int k)
{
// Store answer in the
// bitset Initialized
// with 0
int[] X = new int[32];
// To maintain the count
// of set bits that should
// exceed k
int cnt = 0;
// Start traversing from the
// Most significant if that bit
// is set in n then we will set
// in our answer i.e in X
for(int i = 31; i >= 0 && cnt != k; i--)
{
// Checking if the ith bit
// is set in n or not
if ((n & (1 << i)) != 0)
{
X[i] = 1;
cnt++;
}
}
String s = "";
for(int i = 31; i >= 0; i--)
s += X[i] == 0 ? '0' : '1';
// Converting into integer
return Convert.ToInt32(s, 2);
}
// Driver code
public static void Main(String[] args)
{
int n = 10, k = 2;
// Function Call
Console.Write(find_max(n, k));
}
}
// This code is contributed by offbeat
Javascript
<script>
// javascript program for the
// above approach
// Function to find
// the integer with
// maximum bitwise with N
function find_max(n, k)
{
// Store answer in the
// bitset Initialized
// with 0
var X = Array.from({length: 32}, (_, i) => 0);
// To maintain the count
// of set bits that should
// exceed k
var cnt = 0;
// Start traversing from the
// Most significant if that bit
// is set in n then we will set
// in our answer i.e in X
for (i = 31; i >= 0 &&
cnt != k; i--)
{
// Checking if the ith bit
// is set in n or not
if ((n & (1 << i)) != 0)
{
X[i] = 1;
cnt++;
}
}
var s = "";
for(i = 31; i >= 0; i--)
s += X[i] == 0 ? '0' : '1';
// Converting into integer
return parseInt(s,2);
}
// Driver function
var n = 10, k = 2;
// Function Call
document.write(find_max(n, k));
// This code is contributed by Princi Singh
</script>
10
Análisis de rendimiento:
- Complejidad del tiempo: O(32)
- Espacio Auxiliar: O(1
Publicación traducida automáticamente
Artículo escrito por abhishek_padghan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA