Dados dos enteros A y B , la tarea es verificar si la representación binaria de B se puede generar permutando los dígitos binarios de A .
Ejemplos:
Entrada: A = 3, B = 9
Salida: Sí
Binario(3) = 0011 y Binario(9) = 1001
Entrada: A = 6, B = 7
Salida: No
Enfoque: la idea es contar el número de bits establecidos en las representaciones binarias de ambos números, ahora, si son iguales, la respuesta es Sí o, de lo contrario, la respuesta es No.
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 that returns true if the // binary representation of b can be // generated by permuting the // binary digits of a bool isPossible(int a, int b) { // Find the count of set bits // in both the integers int cntA = __builtin_popcount(a); int cntB = __builtin_popcount(b); // If both the integers have // equal count of set bits if (cntA == cntB) return true; return false; } // Driver code int main() { int a = 3, b = 9; if (isPossible(a, b)) cout << "Yes"; else cout << "No"; return 0; }
Java
// Java implementation of the approach class GFG { // recursive function to count set bits public static int countSetBits(int n) { // base case if (n == 0) return 0; else // if last bit set add 1 else add 0 return (n & 1) + countSetBits(n >> 1); } // Function that returns true if the // binary representation of b can be // generated by permuting the // binary digits of a static boolean isPossible(int a, int b) { // Find the count of set bits // in both the integers int cntA = countSetBits(a); int cntB = countSetBits(b); // If both the integers have // equal count of set bits if (cntA == cntB) return true; return false; } // Driver code public static void main (String[] args) { int a = 3, b = 9; if (isPossible(a, b)) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # function to count set bits def bitsoncount(x): return bin(x).count('1') # Function that returns true if the # binary representation of b can be # generated by permuting the # binary digits of a def isPossible(a, b): # Find the count of set bits # in both the integers cntA = bitsoncount(a); cntB = bitsoncount(b); # If both the integers have # equal count of set bits if (cntA == cntB): return True return False # Driver code a = 3 b = 9 if (isPossible(a, b)): print("Yes") else: print("No") # This code is contributed by Sanjit Prasad
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // recursive function to count set bits public static int countSetBits(int n) { // base case if (n == 0) return 0; else // if last bit set.Add 1 else.Add 0 return (n & 1) + countSetBits(n >> 1); } // Function that returns true if the // binary representation of b can be // generated by permuting the // binary digits of a static bool isPossible(int a, int b) { // Find the count of set bits // in both the integers int cntA = countSetBits(a); int cntB = countSetBits(b); // If both the integers have // equal count of set bits if (cntA == cntB) return true; return false; } // Driver code public static void Main (String[] args) { int a = 3, b = 9; if (isPossible(a, b)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript implementation of the approach // recursive function to count set bits function countSetBits(n) { // base case if (n == 0) return 0; else // if last bit set add 1 else add 0 return (n & 1) + countSetBits(n >> 1); } // Function that returns true if the // binary representation of b can be // generated by permuting the // binary digits of a function isPossible(a, b) { // Find the count of set bits // in both the integers let cntA = countSetBits(a); let cntB = countSetBits(b); // If both the integers have // equal count of set bits if (cntA == cntB) return true; return false; } let a = 3, b = 9; if (isPossible(a, b)) document.write("Yes"); else document.write("No"); // This code is contributed by divyesh072019. </script>
Producción:
Yes
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por DiptayanBiswas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA