Dados dos enteros A y B , la tarea es encontrar un entero X tal que (X XOR A) sea el mínimo posible y el recuento de bits establecidos en X sea igual al recuento de bits establecidos en B.
Ejemplos:
Entrada: A = 3, B = 5
Salida: 3
Binario(A) = Binario(3) = 011
Binario(B) = Binario(5) = 101
El XOR será mínimo cuando M = 3
es decir (3 XOR 3) = 0 y el número
de bits establecidos en 3 es igual
al número de bits establecidos en 5.
Entrada: A = 7, B = 12
Salida: 6
Enfoque: Se sabe que el xor de un elemento consigo mismo es 0. Por lo tanto, intente generar la representación binaria de M lo más cerca posible de A. Atraviese desde el bit más significativo en A hasta el bit menos significativo y si un bit se establece en la posición actual, también debe establecerse en el número requerido para minimizar el XOR, pero el número de bits establecidos debe ser igual al número de bits establecidos en B. Entonces, cuando el recuento de bits establecidos en el número requerido ha alcanzado el recuento de bits establecidos en B, entonces el resto de los bits deben ser 0.
También puede ser posible que el número de bits establecidos en B sea mayor que el número de bits establecidos en A. En este caso, comience a llenar los bits no establecidos para establecer bits desde el bit menos significativo hasta el bit más significativo.
Si el número de bits configurados aún no es igual a B, agregue el número restante de bits configurados a la izquierda del bit más significativo para que los bits configurados de M sean iguales a los bits configurados de B.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the value x
// such that (x XOR a) is minimum
// and the number of set bits in x
// is equal to the number
// of set bits in b
int minVal(int a, int b) {
int setBits=0,res=0;
//To count number of set bits in b
setBits= __builtin_popcount(b);
//creating binary representation of a in stack s
stack<short int> s;
while(a>0)
{
s.push(a%2);
a=a/2;
}
// Decrease the count of setBits
// as in the required number set bits has to be
// equal to the count of set bits in b
//Creating nearest possible number in m in binary form.
//Using vector as the number in binary for can be large.
vector<short int> m;
while(!s.empty())
{
if(s.top()==1 && setBits>0)
{
m.push_back(1);
setBits--;
}
else
{
m.push_back(0);
}
s.pop();
}
//Filling the unset bits from the least significant bit to the most significant bit
//if the setBits are not equal to zero
for(int i=m.size()-1;i>=0 && setBits>0;i--)
{
if(m[i]==0)
{
m[i]=1;
setBits--;
}
}
int mask;
for(int i=m.size()-1;i>=0;i--)
{
mask=1<<(m.size()-i-1);
res+=m[i]*mask;
}
int n=m.size();
//if the number of setBits is still not equal to zero
//dd the remaining number of set bits to the left of the most significant bit
//in order to make set bits of m equal to the set bits of B.
while(setBits>0)
{
res+=1<<n;
n++;
setBits--;
}
return res;
}
// Driver code
int main()
{
int a = 3, b = 5;
cout << minVal(a, b);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to get no of set
// bits in binary representation
// of positive integer n
static int countSetBits(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Function to return the value x
// such that (x XOR a) is minimum
// and the number of set bits in x
// is equal to the number
// of set bits in b
static int minVal(int a, int b)
{
// Count of set-bits in bit
int setBits = countSetBits(b);
int ans = 0;
for (int i = 30; i >= 0; i--)
{
int mask = 1 << i;
// If i'th bit is set also set the
// same bit in the required number
if ((a & mask) > 0 && setBits > 0)
{
ans |= (1 << i);
// Decrease the count of setbits
// in b as the count of set bits
// in the required number has to be
// equal to the count of set bits in b
setBits--;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int a = 3, b = 5;
System.out.println(minVal(a, b));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach
# Function to return the value x
# such that (x XOR a) is minimum
# and the number of set bits in x
# is equal to the number
# of set bits in b
def minVal(a, b):
# Count of set-bits in bit
setBits = bin(b).count('1')
ans = 0
for i in range(30, -1, -1):
mask = (1 << i)
s = (a & mask)
# If i'th bit is set also set the
# same bit in the required number
if (s and setBits > 0):
ans |= (1 << i)
# Decrease the count of setbits
# in b as the count of set bits
# in the required number has to be
# equal to the count of set bits in b
setBits -= 1
i = 0
# we need to check for remaining set bits
# we can assign remaining set bits to least significant bits
while(setBits > 0):
mask = (1 << i)
if (ans & mask) == 0:
ans |= (1 << i)
setBits -= 1
i += 1
return ans
# Driver code
if __name__ == "__main__":
a = 3
b = 5
print(minVal(a, b))
# This code is contributed by kanugargng
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to get no of set
// bits in binary representation
// of positive integer n
static int countSetBits(int n)
{
int count = 0;
while (n > 0)
{
count += n & 1;
n >>= 1;
}
return count;
}
// Function to return the value x
// such that (x XOR a) is minimum
// and the number of set bits in x
// is equal to the number
// of set bits in b
static int minVal(int a, int b)
{
// Count of set-bits in bit
int setBits = countSetBits(b);
int ans = 0;
for (int i = 30; i >= 0; i--)
{
int mask = 1 << i;
// If i'th bit is set also set the
// same bit in the required number
if ((a & mask) > 0 && setBits > 0)
{
ans |= (1 << i);
// Decrease the count of setbits
// in b as the count of set bits
// in the required number has to be
// equal to the count of set bits in b
setBits--;
}
}
return ans;
}
// Driver Code
public static void Main()
{
int a = 3, b = 5;
Console.Write(minVal(a, b));
}
}
// This code is contributed by Mohit kumar 29
Javascript
<script>
// Javascript implementation of the approach
// Function to get no of set
// bits in binary representation
// of positive integer n
function countSetBits(n) {
let count = 0;
while (n > 0) {
count += n & 1;
n >>= 1;
}
return count;
}
// Function to return the value x
// such that (x XOR a) is minimum
// and the number of set bits in x
// is equal to the number
// of set bits in b
function minVal(a, b)
{
// Count of set-bits in bit
let setBits = countSetBits(b);
let ans = 0;
for (let i = 30; i >= 0; i--) {
let mask = 1 << i;
// If i'th bit is set also set the
// same bit in the required number
if ((a & mask) > 0 && setBits > 0) {
ans |= (1 << i);
// Decrease the count of setbits
// in b as the count of set bits
// in the required number has to be
// equal to the count of set bits in b
setBits--;
}
}
return ans;
}
// Driver Code
let a = 3, b = 5;
document.write(minVal(a, b));
// This code is contributed by gfgking.
</script>
3
Complejidad del tiempo: O(log(N))
Espacio auxiliar: O(log(N))
2. Enfoque eficiente del espacio
Mediante la teoría de la manipulación de bits, el Xor de dos valores se minimizará si tienen los mismos bits. Al usar esta teoría, dividiremos este problema en 3 partes de la siguiente manera:
Uno es si los bits establecidos de A y B son iguales. En segundo lugar, si los bits establecidos de A son mayores que B. En tercer lugar, si los bits establecidos de B son mayores que A. Si los bits establecidos son iguales, devolveremos A. Si cae en el segundo caso, eliminaremos el número de diferencia de bits inferiores de A. Si cae en el tercer caso, agregaremos los bits inferiores de A si el bit no está configurado en A.
Complejidad
Tiempo Complejidad necesitamos iterar a todos los bits presentes en A y B. El número máximo de bits es 30, por lo que la complejidad es O(log(max(A,B))).
Complejidad espacial Solo necesitamos iterar sobre los 30 bits y almacenar la respuesta para que la complejidad sea O(1).
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
int minVal(int a, int b) {
// code here
int setb= __builtin_popcount(b);
int seta= __builtin_popcount(a);
int ans=0;
for(int i=0;i<=31;i++){
int mask=1<<i;
int set= a & mask;
if(set==0 && setb>seta){
ans |=(mask);
setb--;
}
else if(set && seta>setb) seta--;
else ans|=set;
}
return ans;
}
int main()
{
int a = 7, b = 12;
cout << minVal(a, b);
return 0;
}
Python3
# python3 code for the above approach:
def minVal(a, b):
# code here
setb = bin(b)[2:].count('1')
seta = bin(a)[2:].count('1')
ans = 0
for i in range(0, 32):
mask = 1 << i
set = a & mask
if(set == 0 and setb > seta):
ans |= (mask)
setb -= 1
elif(set and seta > setb):
seta -= 1
else:
ans |= set
return ans
if __name__ == "__main__":
a = 7
b = 12
print(minVal(a, b))
# This code is contributed by rakeshsahni
6
Publicación traducida automáticamente
Artículo escrito por Adityasharma15 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA