Dados dos enteros positivos A y B, podemos cambiar como máximo K bits en ambos números para hacer que OR sea igual a un número objetivo dado T. En el caso de soluciones múltiples, trate de mantener A lo más pequeño posible. Ejemplos:
Input : A = 175,
B = 66,
T = 100,
K = 5
Output : A = 36
B = 64
Initial bits of A = 1010 1111
Changed bits of A = 0010 0100
Initial bits of B = 0100 0010
Changed bits of B = 0100 0000
OR of changed Bits = 0110 0100
Which has decimal value equal to Target T.
Input : A = 175,
B = 66,
T = 100,
K = 4
Output : Not Possible
It is not possible to get OR of
A and B as T, just by changing K bits.
Podemos resolver este problema iterando sobre todos los bits de A y B y cambiándolos con avidez, es decir,
- Si el bit i-ésimo de Target T es 0, entonces establezca los bits i-ésimo de A y B en 0 (si no lo está ya)
- Si el i-ésimo bit de Target T es 1, intentaremos establecer uno de los bits en 1 y cambiaremos el i-ésimo bit de B solo a 1 (si no lo está ya) para minimizar A.
Después del procedimiento anterior, si los bits cambiados son más que K , entonces no es posible obtener OR de A y B como T cambiando como máximo K bits. Si los bits cambiados son menores que k , entonces podemos minimizar aún más el valor de A usando el valor restante de K para el cual repetiremos los bits una vez más y, si en cualquier momento,
- El i-ésimo bit A es 1 y el i-ésimo bit B es 0, entonces haremos 2 cambios y voltearemos ambos.
- Los i-ésimos bits A y B son 1, luego nuevamente haremos 1 cambio y voltearemos el bit A.
La complejidad de tiempo total de la solución anterior será O (número máximo de bits).
C++
// C++ program to change least bits to
// get desired OR value
#include <bits/stdc++.h>
using namespace std;
// Returns max of three numbers
int max(int a, int b, int c)
{
return max(a, max(b, c));
}
// Returns count of bits in N
int bitCount(int N)
{
int cnt = 0;
while (N)
{
cnt++;
N >>= 1;
}
return cnt;
}
// Returns bit at 'pos' position
bool at_position(int num, int pos)
{
bool bit = num & (1<<pos);
return bit;
}
// Utility method to toggle bit at
// 'pos' position
void toggle(int &num,int pos)
{
num ^= (1 << pos);
}
// method returns minimum number of bit flip
// to get T as OR value of A and B
void minChangeToReachTaregetOR(int A, int B,
int K, int T)
{
int maxlen = max(bitCount(A), bitCount(B),
bitCount(T));
// Loop over maximum number of bits among
// A, B and T
for (int i = maxlen - 1; i >= 0; i--)
{
bool bitA = at_position(A, i);
bool bitB = at_position(B, i);
bool bitT = at_position(T, i);
// T's bit is set, try to toggle bit
// of B, if not already
if (bitT)
{
if (!bitA && !bitB)
{
toggle(B, i);
K--;
}
}
else
{
// if A's bit is set, flip that
if (bitA)
{
toggle(A, i);
K--;
}
// if B's bit is set, flip that
if (bitB)
{
toggle(B, i);
K--;
}
}
}
// if K is less than 0 then we can make A|B == T
if (K < 0)
{
cout << "Not possible\n";
return;
}
// Loop over bits one more time to minimise
// A further
for (int i = maxlen - 1; K > 0 && i >= 0; --i)
{
bool bitA = at_position(A, i);
bool bitB = at_position(B, i);
bool bitT = at_position(T, i);
if (bitT)
{
// If both bit are set, then Unset
// A's bit to minimise it
if (bitA && bitB)
{
toggle(A, i);
K--;
}
}
// If A's bit is 1 and B's bit is 0,
// toggle both
if (bitA && !bitB && K >= 2)
{
toggle(A, i);
toggle(B, i);
K -= 2;
}
}
// Output changed value of A and B
cout << A << " " << B << endl;
}
// Driver code
int main()
{
int A = 175, B = 66, K = 5, T = 100;
minChangeToReachTaregetOR(A, B, K, T);
return 0;
}
Java
// Java program to change least bits to
// get desired OR value
class GFG {
// Returns max of three numbers
static int max(int a, int b, int c)
{
return Math.max(a, Math.max(b, c));
}
// Returns count of bits in N
static int bitCount(int N)
{
int cnt = 0;
while (N != 0)
{
cnt++;
N >>= 1;
}
return cnt;
}
// Returns bit at 'pos' position
static int at_position(int num, int pos)
{
int bit = num & (1<<pos);
return bit;
}
// Utility method to toggle bit at
// 'pos' position
static int toggle(int num,int pos)
{
num ^= (1 << pos);
return num;
}
// method returns minimum number of bit flip
// to get T as OR value of A and B
static void minChangeToReachTaregetOR(int A, int B,
int K, int T)
{
int maxlen = max(bitCount(A), bitCount(B),
bitCount(T));
// Loop over maximum number of bits among
// A, B and T
for (int i = maxlen - 1; i >= 0; i--)
{
int bitA = at_position(A, i);
int bitB = at_position(B, i);
int bitT = at_position(T, i);
// T's bit is set, try to toggle bit
// of B, if not already
if (bitT != 0)
{
if ((bitA == 0) && (bitB == 0))
{
B = toggle(B, i);
K--;
}
}
else
{
// if A's bit is set, flip that
if (bitA != 0)
{
A = toggle(A, i);
K--;
}
// if B's bit is set, flip that
if (bitB != 0)
{
B = toggle(B, i);
K--;
}
}
}
// if K is less than 0 then we can make A|B == T
if (K < 0)
{
System.out.println("Not possible");
return;
}
// Loop over bits one more time to minimise
// A further
for (int i = maxlen - 1; K > 0 && i >= 0; --i)
{
int bitA = at_position(A, i);
int bitB = at_position(B, i);
int bitT = at_position(T, i);
if (bitT != 0)
{
// If both bit are set, then Unset
// A's bit to minimise it
if ((bitA != 0) && (bitB != 0))
{
toggle(A, i);
K--;
}
}
// If A's bit is 1 and B's bit is 0,
// toggle both
if ((bitA != 0) && (bitB == 0) && K >= 2)
{
toggle(A, i);
toggle(B, i);
K -= 2;
}
}
// Output changed value of A and B
System.out.println(A + " " + B);
}
//Driver Code
public static void main(String[] args) {
int A = 175, B = 66, K = 5, T = 100;
minChangeToReachTaregetOR(A, B, K, T);
}
}
//This code is contributed by phasing17
Python3
# Python3 program to change least bits to
# get desired OR value
# Returns count of bits in N
def bitCount(N):
cnt = 0;
while (N > 0):
cnt += 1
N >>= 1
return cnt
# Returns bit at 'pos' position
def at_position(num, pos):
bit = num & (1<<pos)
return (bit != 0)
# Utility method to toggle bit at
# 'pos' position
def toggle(num, pos):
num ^= (1 << pos)
return num
# method returns minimum number of bit flip
# to get T as OR value of A and B
def minChangeToReachTaregetOR(A, B, K, T):
maxlen = max(bitCount(A), bitCount(B), bitCount(T));
# Loop over maximum number of bits among
# A, B and T
for i in range(maxlen - 1, -1, -1):
bitA = at_position(A, i);
bitB = at_position(B, i);
bitT = at_position(T, i);
# T's bit is set, try to toggle bit
# of B, if not already
if (bitT > 0):
if ((not bitA) and (not bitB)):
B = toggle(B, i)
K -= 1
else:
# if A's bit is set, flip that
if (bitA > 0):
A = toggle(A, i)
K -= 1
# if B's bit is set, flip that
if (bitB > 0):
B = toggle(B, i)
K -= 1
# if K is less than 0 then we can make A|B == T
if (K < 0):
print("Not possible");
return;
# Loop over bits one more time to minimise
# A further
i = maxlen - 1
while True:
if K < 0 or i < 0:
break
bitA = at_position(A, i);
bitB = at_position(B, i);
bitT = at_position(T, i);
if (bitT > 0):
# If both bit are set, then Unset
# A's bit to minimise it
if (bitA and bitB):
A = toggle(A, i)
K -= 1
# If A's bit is 1 and B's bit is 0,
# toggle both
if ((bitA != 0) and (not bitB) and K >= 2):
A = toggle(A, i)
B = toggle(B, i)
K -= 2
i -= 1
# Output changed value of A and B
print(A, B)
# Driver code
A = 175
B = 66
K = 5
T = 100
minChangeToReachTaregetOR(A, B, K, T)
# This code is contributed by phasing17
C#
// C# program to change least bits to
// get desired OR value
using System;
class GFG {
// Returns max of three numbers
static int max(int a, int b, int c)
{
return Math.Max(a, Math.Max(b, c));
}
// Returns count of bits in N
static int bitCount(int N)
{
int cnt = 0;
while (N != 0) {
cnt++;
N >>= 1;
}
return cnt;
}
// Returns bit at 'pos' position
static int at_position(int num, int pos)
{
int bit = num & (1 << pos);
return bit;
}
// Utility method to toggle bit at
// 'pos' position
static int toggle(int num, int pos)
{
num ^= (1 << pos);
return num;
}
// method returns minimum number of bit flip
// to get T as OR value of A and B
static void minChangeToReachTaregetOR(int A, int B,
int K, int T)
{
int maxlen
= max(bitCount(A), bitCount(B), bitCount(T));
// Loop over maximum number of bits among
// A, B and T
for (int i = maxlen - 1; i >= 0; i--) {
int bitA = at_position(A, i);
int bitB = at_position(B, i);
int bitT = at_position(T, i);
// T's bit is set, try to toggle bit
// of B, if not already
if (bitT != 0) {
if ((bitA == 0) && (bitB == 0)) {
B = toggle(B, i);
K--;
}
}
else {
// if A's bit is set, flip that
if (bitA != 0) {
A = toggle(A, i);
K--;
}
// if B's bit is set, flip that
if (bitB != 0) {
B = toggle(B, i);
K--;
}
}
}
// if K is less than 0 then we can make A|B == T
if (K < 0) {
Console.WriteLine("Not possible");
return;
}
// Loop over bits one more time to minimise
// A further
for (int i = maxlen - 1; K > 0 && i >= 0; --i) {
int bitA = at_position(A, i);
int bitB = at_position(B, i);
int bitT = at_position(T, i);
if (bitT != 0) {
// If both bit are set, then Unset
// A's bit to minimise it
if ((bitA != 0) && (bitB != 0)) {
toggle(A, i);
K--;
}
}
// If A's bit is 1 and B's bit is 0,
// toggle both
if ((bitA != 0) && (bitB == 0) && K >= 2) {
toggle(A, i);
toggle(B, i);
K -= 2;
}
}
// Output changed value of A and B
Console.WriteLine(A + " " + B);
}
// Driver Code
public static void Main(string[] args)
{
int A = 175, B = 66, K = 5, T = 100;
minChangeToReachTaregetOR(A, B, K, T);
}
}
// This code is contributed by phasing17
PHP
<?php
// PHP program to change least
// bits to get desired OR value
// Returns max of three numbers
function maxDD($a, $b, $c)
{
return max($a, (max($b, $c)));
}
// Returns count of bits in N
function bitCount($N)
{
$cnt = 0;
while ($N)
{
$cnt++;
$N >>= 1;
}
return $cnt;
}
// Returns bit at 'pos' position
function at_position($num, $pos)
{
$bit = $num & (1 << $pos);
return $bit;
}
// Utility method to toggle
// bit at 'pos' position
function toggle(&$num, $pos)
{
$num ^= (1 << $pos);
}
// method returns minimum
// number of bit flip to
// get T as OR value of A and B
function minChangeToReachTaregetOR($A, $B,
$K, $T)
{
$maxlen = max(bitCount($A),
bitCount($B),
bitCount($T));
// Loop over maximum number
// of bits among A, B and T
for ( $i = $maxlen - 1; $i >= 0; $i--)
{
$bitA = at_position($A, $i);
$bitB = at_position($B, $i);
$bitT = at_position($T, $i);
// T's bit is set, try to toggle
// bit of B, if not already
if ($bitT)
{
if (!$bitA && !$bitB)
{
toggle($B, $i);
$K--;
}
}
else
{
// if A's bit is set,
// flip that
if ($bitA)
{
toggle($A, $i);
$K--;
}
// if B's bit is set,
// flip that
if ($bitB)
{
toggle($B, $i);
$K--;
}
}
}
// if K is less than 0 then
// we can make A|B == T
if ($K < 0)
{
echo "Not possible\n";
return;
}
// Loop over bits one more
// time to minimise A further
for ($i = $maxlen - 1;
$K > 0 && $i >= 0; --$i)
{
$bitA = at_position($A, $i);
$bitB = at_position($B, $i);
$bitT = at_position($T, $i);
if ($bitT)
{
// If both bit are set, then
// Unset A's bit to minimise it
if ($bitA && $bitB)
{
toggle($A, $i);
$K--;
}
}
// If A's bit is 1 and B's
// bit is 0, toggle both
if ($bitA && !$bitB && $K >= 2)
{
toggle($A, $i);
toggle($B, $i);
$K -= 2;
}
}
// Output changed value
// of A and B
echo $A , " " , $B , "\n";
}
// Driver Code
$A = 175;
$B = 66;
$K = 5;
$T = 100;
minChangeToReachTaregetOR($A, $B, $K, $T);
// This code is contributed by ajit
?>
Javascript
// JavaScript program to change least bits to
// get desired OR value
// Returns max of three numbers
function max(a, b, c)
{
return Math.max(a, Math.max(b, c));
}
// Returns count of bits in N
function bitCount(N)
{
let cnt = 0;
while (N > 0)
{
cnt++;
N >>= 1;
}
return cnt;
}
// Returns bit at 'pos' position
function at_position(num, pos)
{
let bit = num & (1<<pos);
return (bit != 0) ? true : false;
}
// Utility method to toggle bit at
// 'pos' position
function toggle(num, pos)
{
num ^= (1 << pos);
return num;
}
// method returns minimum number of bit flip
// to get T as OR value of A and B
function minChangeToReachTaregetOR(A, B, K, T)
{
let maxlen = Math.max(bitCount(A), bitCount(B),
bitCount(T));
// Loop over maximum number of bits among
// A, B and T
for (let i = maxlen - 1; i >= 0; i--)
{
let bitA = at_position(A, i);
let bitB = at_position(B, i);
let bitT = at_position(T, i);
// T's bit is set, try to toggle bit
// of B, if not already
if (bitT )
{
if ((!bitA) && (!bitB))
{
B = toggle(B, i);
K--;
}
}
else
{
// if A's bit is set, flip that
if (bitA)
{
A = toggle(A, i);
K--;
}
// if B's bit is set, flip that
if (bitB)
{
B = toggle(B, i);
K--;
}
}
}
// if K is less than 0 then we can make A|B == T
if (K < 0)
{
console.log("Not possible");
return;
}
// Loop over bits one more time to minimise
// A further
for (let i = maxlen - 1; K > 0 && i >= 0; --i)
{
let bitA = at_position(A, i);
let bitB = at_position(B, i);
let bitT = at_position(T, i);
if (bitT)
{
// If both bit are set, then Unset
// A's bit to minimise it
if (bitA && bitB)
{
A = toggle(A, i);
K--;
}
}
// If A's bit is 1 and B's bit is 0,
// toggle both
if (bitA && !bitB && K >= 2)
{
A = toggle(A, i);
B = toggle(B, i);
K -= 2;
}
}
// Output changed value of A and B
console.log(A, B);
}
// Driver code
let A = 175, B = 66, K = 5, T = 100;
minChangeToReachTaregetOR(A, B, K, T);
//This code is contributed by phasing17
Producción :
36 64
Complejidad de tiempo: O(log(max({A, B, T})))
Espacio Auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA