Dados dos enteros positivos A y B , realice una de las siguientes operaciones solo una vez para igualar los números.
- Cambiar el i-ésimo bit de un número a 0 o 1
- Cambie el i-ésimo bit a 0 o 1 en A y el j-ésimo bit a 0 o 1 en B
Si es posible hacer que los números sean iguales, imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: A = 5, B = 15
Salida: Sí
Explicación: Las representaciones binarias de los números 5 y 15 son 0101 y 1111 respectivamente.
Ahora, cambie el cuarto bit del número 5 a 1 y el segundo bit del número 15 a 0.
Por lo tanto, ambos números se vuelven iguales, es decir, 13.Entrada: A = 8, B = 7
Salida: No
Enfoque: El problema dado se puede resolver contando la diferencia de bits establecidos en ambos números, es decir, en cuántas posiciones los bits de ambos números son diferentes entre sí. Si la cuenta es más de dos , entonces no es posible hacer que los números sean iguales.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if it
// is possible to make the two
// numbers equal or not
#include <bits/stdc++.h>
using namespace std;
// Function to count the different bits
// in both numbers
void makeNumbersEqual(int A, int B)
{
// Stores the number of different bits
int diff = 0;
// Stores the binary representations of
// a and b respectively
bitset<32> ar(A), br(B);
for (int i = 0; i < 32; i++) {
if (ar[i] != br[i])
diff++;
}
if (diff <= 2)
cout << "Yes";
else
cout << "No";
}
// Driver Code
int main()
{
int A = 5, B = 15;
makeNumbersEqual(A, B);
return 0;
}
Java
// java code for the above approach
class GFG
{
// Function to count the different bits
// in both numbers
static void makeNumbersEqual(int A, int B) {
// Stores the number of different bits
int diff = 0;
// Stores the binary representations of
// a and b respectively
int[] ar = new int[32];
int[] br = new int[32];
for (int i = 0; i < 32; i++) {
ar[i] = 0;
br[i] = 0;
}
for (int i = 0; i < 32; i++) {
if ((A & (1 << i)) == 0) {
ar[i]++;
}
if ((B & (1 << i)) == 0) {
br[i]++;
}
}
for (int i = 0; i < 32; i++) {
if (ar[i] != br[i])
diff++;
}
if (diff <= 2)
System.out.print("Yes");
else
System.out.print("No");
}
// Driver Code
public static void main(String args[]) {
int A = 5, B = 15;
makeNumbersEqual(A, B);
}
}
// This code is contributed by gfgking
Python3
# Python code for the above approach
# Function to count the different bits
# in both numbers
def makeNumbersEqual(A, B):
# Stores the number of different bits
diff = 0;
# Stores the binary representations of
# a and b respectively
ar = [0] * 32
br = [0] * 32
for i in range(32):
if (A & (1 << i)):
ar[i] += 1
if (B & (1 << i)):
br[i] += 1
for i in range(32):
if (ar[i] != br[i]):
diff += 1
if (diff <= 2):
print("Yes");
else:
print("No");
# Driver Code
A = 5
B = 15;
makeNumbersEqual(A, B);
# This code is contributed by Saurabh Jaiswal
C#
// C# code for the above approach
using System;
class GFG {
// Function to count the different bits
// in both numbers
static void makeNumbersEqual(int A, int B)
{
// Stores the number of different bits
int diff = 0;
// Stores the binary representations of
// a and b respectively
int[] ar = new int[32];
int[] br = new int[32];
for (int i = 0; i < 32; i++) {
ar[i] = 0;
br[i] = 0;
}
for (int i = 0; i < 32; i++) {
if ((A & (1 << i)) == 0) {
ar[i]++;
}
if ((B & (1 << i)) == 0) {
br[i]++;
}
}
for (int i = 0; i < 32; i++) {
if (ar[i] != br[i])
diff++;
}
if (diff <= 2)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver Code
public static void Main()
{
int A = 5, B = 15;
makeNumbersEqual(A, B);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to count the different bits
// in both numbers
function makeNumbersEqual(A, B)
{
// Stores the number of different bits
let diff = 0;
// Stores the binary representations of
// a and b respectively
let ar = new Array(32).fill(0), br = new Array(32).fill(0);
for (let i = 0; i < 32; i++) {
if (A & (1 << i)) {
ar[i]++;
}
if (B & (1 << i)) {
br[i]++;
}
}
for (let i = 0; i < 32; i++) {
if (ar[i] != br[i])
diff++;
}
if (diff <= 2)
document.write("Yes");
else
document.write("No");
}
// Driver Code
let A = 5, B = 15;
makeNumbersEqual(A, B);
// This code is contributed by Potta Lokesh
</script>
Yes
Complejidad de tiempo : si asumimos que los números tienen solo 32 bits, entonces la complejidad de tiempo será O (1). pero los números pueden tener N bits de longitud… por lo que la complejidad temporal en ese caso será O(N).
Espacio auxiliar : si los números tienen una longitud de N bits, entonces el espacio requerido sería O (N) para almacenar su representación binaria. Si las longitudes máximas de la representación binaria de A y B son 32, entonces solo la complejidad del espacio sería O(1).
Enfoque eficiente: como tenemos que contar el número de bits diferentes en A y B… Entonces, usaremos la propiedad XOR aquí y generaremos un número que tiene solo bits establecidos que son diferentes en A y B.
entonces haremos X=A^B, luego los bits establecidos en X serán aquellos bits que son diferentes en A y B.
Ahora nuestro trabajo es contar el número de bits establecidos en X.
C++
// C++ program to check if it
// is possible to make the two
// numbers equal or not
#include <bits/stdc++.h>
using namespace std;
string makeNumbersEqual(int A, int B){
// Find Xor of A and B
int X = A ^ B;
// variable to count total set bits in X.
int count_setBits = 0;
// loop to check whether X has more than 2
// set bits or not.If count_setBits is
// more than 2 then return No.
while (X > 0){
if ((X & 1) == 1 )
count_setBits += 1;
// checking count of set bits at each iteration
if (count_setBits > 2)
return "No";
// making X half at each time.
X /= 2;
}
return "Yes";
}
// Driver Code
int main()
{
int A = 5, B = 15;
cout << makeNumbersEqual(A, B);
return 0;
}
// This code is contributed by jana_sayantan.
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
static String makeNumbersEqual(int A, int B){
// Find Xor of A and B
int X = A ^ B;
// variable to count total set bits in X.
int count_setBits = 0;
// loop to check whether X has more than 2
// set bits or not.If count_setBits is
// more than 2 then return No.
while (X > 0){
if ((X & 1) == 1 )
count_setBits += 1;
// checking count of set bits at each iteration
if (count_setBits > 2)
return "No";
// making X half at each time.
X /= 2;
}
return "Yes";
}
// Driver Code
public static void main (String[] args) {
int A = 5;
int B = 15;
System.out.print(makeNumbersEqual(A, B));
}
}
// This code is contributed by code_hunt.
Python3
# Python code for the above approach # Function to count the different bits # in both numbers def makeNumbersEqual(A, B): # Find Xor of A and B X = A ^ B # variable to count total set bits in X. count_setBits = 0 # loop to check whether X has more than 2 # set bits or not.If count_setBits is # more than 2 then return No. while X > 0: if X & 1 == 1: count_setBits += 1 # checking count of set bits at each iteration if count_setBits > 2: return 'No' # making X half at each time. X //= 2 return 'Yes' # Driver Code. A = 5 B = 15 print(makeNumbersEqual(A, B)) '''Code is written by Rajat Kumar'''
C#
// C# program for the above approach
using System;
public class GFG
{
static string makeNumbersEqual(int A, int B)
{
// Find Xor of A and B
int X = A ^ B;
// variable to count total set bits in X.
int count_setBits = 0;
// loop to check whether X has more than 2
// set bits or not.If count_setBits is
// more than 2 then return No.
while (X > 0) {
if ((X & 1) == 1)
count_setBits += 1;
// checking count of set bits at each iteration
if (count_setBits > 2)
return "No";
// making X half at each time.
X /= 2;
}
return "Yes";
}
public static void Main(string[] args)
{
int A = 5;
int B = 15;
Console.WriteLine(makeNumbersEqual(A, B));
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript code to implement the above approach
function makeNumbersEqual(A, B)
{
// Find Xor of A and B
let X = A ^ B
// variable to count total set bits in X.
let count_setBits = 0
// loop to check whether X has more than 2
// set bits or not.If count_setBits is
// more than 2 then return No.
while(X > 0)
{
if(X & 1 == 1)
{
count_setBits += 1
// checking count of set bits at each iteration
if(count_setBits > 2)
return 'No'
}
// making X half at each time.a
X = Math.floor(X/2)
}
return 'Yes'
}
// Driver Code.
let A = 5
let B = 15
document.write(makeNumbersEqual(A, B))
// This code is contributed by shinjanpatra
</script>
Yes
Complejidad de tiempo : no importa cuán largos sean A y B, la complejidad de tiempo sería O (log (max (A, B))) en el peor de los casos.
En el caso promedio, la complejidad del tiempo sería O (1) ya que necesitamos contar solo 2 bits establecidos.
Complejidad espacial: O(1) Siempre.
Publicación traducida automáticamente
Artículo escrito por abhishekmaran1947 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA