Check if binary representations of two numbers are anagram
Given two numbers you are required to check whether they are anagrams of each other or not in binary representation.
Examples:
Input : a = 8, b = 4 Output : Yes Binary representations of both numbers have same 0s and 1s. Input : a = 4, b = 5 Output : No
Simple Approach:
- Find the Binary Representation of ‘a’ and ‘b’ using a simple decimal-to-binary representation technique.
- Check if two binary representations are an anagram
Below is the implementation of the above approach:
C++
// A simple C++ program to check if binary // representations of two numbers are anagram. #include <bits/stdc++.h> #define ull unsigned long long int using namespace std; const int SIZE = 8 * sizeof (ull); bool bit_anagram_check(ull a, ull b) { // Find reverse binary representation of a // and store it in binary_a[] int i = 0, binary_a[SIZE] = { 0 }; while (a > 0) { binary_a[i] = a % 2; a /= 2; i++; } // Find reverse binary representation of b // and store it in binary_a[] int j = 0, binary_b[SIZE] = { 0 }; while (b > 0) { binary_b[j] = b % 2; b /= 2; j++; } // Sort two binary representations sort(binary_a, binary_a + SIZE); sort(binary_b, binary_b + SIZE); // Compare two sorted binary representations for ( int i = 0; i < SIZE; i++) if (binary_a[i] != binary_b[i]) return false ; return true ; } // Driver code int main() { ull a = 8, b = 4; cout << bit_anagram_check(a, b) << endl; return 0; } |
Java
// A simple Java program to check if binary // representations of two numbers are anagram import java.io.*; import java.util.*; class GFG { public static int SIZE = 8 ; // Function to check if binary representation // of two numbers are anagram static int bit_anagram_check( long a, long b) { // Find reverse binary representation of a // and store it in binary_a[] int i = 0 ; long [] binary_a = new long [SIZE]; Arrays.fill(binary_a, 0 ); while (a > 0 ) { binary_a[i] = a% 2 ; a /= 2 ; i++; } // Find reverse binary representation of b // and store it in binary_a[] int j = 0 ; long [] binary_b = new long [SIZE]; Arrays.fill(binary_b, 0 ); while (b > 0 ) { binary_b[j] = b% 2 ; b /= 2 ; j++; } // Sort two binary representations Arrays.sort(binary_a); Arrays.sort(binary_b); // Compare two sorted binary representations for (i = 0 ; i < SIZE; i++) if (binary_a[i] != binary_b[i]) return 0 ; return 1 ; } // driver program public static void main (String[] args) { long a = 8 , b = 4 ; System.out.println(bit_anagram_check(a, b)); } } // Contributed by Pramod Kumar |
Python3
# A simple Python program to check if binary # representations of two numbers are anagram. SIZE = 8 def bit_anagram_check(a, b): # Find reverse binary representation of a # and store it in binary_a[] global size i = 0 binary_a = [ 0 ] * SIZE while (a > 0 ): binary_a[i] = a % 2 a / / = 2 i + = 1 # Find reverse binary representation of b # and store it in binary_a[] j = 0 binary_b = [ 0 ] * SIZE while (b > 0 ): binary_b[j] = b % 2 b / / = 2 j + = 1 # Sort two binary representations binary_a.sort() binary_b.sort() # Compare two sorted binary representations for i in range (SIZE): if (binary_a[i] ! = binary_b[i]): return 0 return 1 # Driver code if __name__ = = "__main__" : a = 8 b = 4 print (bit_anagram_check(a, b)) # This code is contributed by ukasp. |
C#
// A simple C# program to check if // binary representations of two // numbers are anagram using System; class GFG { public static int SIZE = 8; // Function to check if binary // representation of two numbers // are anagram public static int bit_anagram_check( long a, long b) { // Find reverse binary representation // of a and store it in binary_a[] int i = 0; long [] binary_a = new long [SIZE]; Arrays.Fill(binary_a, 0); while (a > 0) { binary_a[i] = a % 2; a /= 2; i++; } // Find reverse binary representation // of b and store it in binary_a[] int j = 0; long [] binary_b = new long [SIZE]; Arrays.Fill(binary_b, 0); while (b > 0) { binary_b[j] = b % 2; b /= 2; j++; } // Sort two binary representations Array.Sort(binary_a); Array.Sort(binary_b); // Compare two sorted binary // representations for (i = 0; i < SIZE; i++) { if (binary_a[i] != binary_b[i]) { return 0; } } return 1; } public static class Arrays { public static T[] CopyOf<T>(T[] original, int newLength) { T[] dest = new T[newLength]; System.Array.Copy(original, dest, newLength); return dest; } public static T[] CopyOfRange<T>(T[] original, int fromIndex, int toIndex) { int length = toIndex - fromIndex; T[] dest = new T[length]; System.Array.Copy(original, fromIndex, dest, 0, length); return dest; } public static void Fill<T>(T[] array, T value) { for ( int i = 0; i < array.Length; i++) { array[i] = value; } } public static void Fill<T>(T[] array, int fromIndex, int toIndex, T value) { for ( int i = fromIndex; i < toIndex; i++) { array[i] = value; } } } // Driver Code public static void Main( string [] args) { long a = 8, b = 4; Console.WriteLine(bit_anagram_check(a, b)); } } // This code is contributed by Shrikant13 |
Javascript
<script> // A simple Javascript program to check if binary // representations of two numbers are anagram let SIZE = 8; // Function to check if binary representation // of two numbers are anagram function bit_anagram_check(a,b) { // Find reverse binary representation of a // and store it in binary_a[] let i = 0; let binary_a = new Array(SIZE); for (let i=0;i<SIZE;i++) { binary_a[i]=0; } while (a > 0) { binary_a[i] = a%2; a = Math.floor(a/2); i++; } // Find reverse binary representation of b // and store it in binary_a[] let j = 0; let binary_b = new Array(SIZE); for (let i=0;i<SIZE;i++) { binary_b[i]=0; } while (b > 0) { binary_b[j] = b%2; b = Math.floor(b/2); j++; } // Sort two binary representations binary_a.sort( function (a,b){ return a-b;}); binary_b.sort( function (a,b){ return a-b;}); // Compare two sorted binary representations for (i = 0; i < SIZE; i++) if (binary_a[i] != binary_b[i]) return 0; return 1; } // driver program let a = 8, b = 4; document.write(bit_anagram_check(a, b)); //This code is contributed by rag2127 </script> |
Output
1
Note that the above code uses GCC-specific functions. If we wish to write code for other compilers, we may use Count set bits in an integer.
Time Complexity: O (1)
Auxiliary Space: O (1) No extra space is getting used.
Another Approach: If the number of set bits in two numbers is equal, then their binary representations are anagrams.
Below is the implementation of the above approach:
C++
// C++ program to check if binary // representations of two numbers are anagrams. #include <bits/stdc++.h> using namespace std; // Check each bit in a number is set or not // and return the total count of the set bits. int countSetBits( int n) { int count = 0; while (n) { count += n & 1; n >>= 1; } return count; } bool areAnagrams( int A, int B) { return countSetBits(A) == countSetBits(B); } // Driver code int main() { int a = 8, b = 4; cout << areAnagrams(a, b) << endl; return 0; } // This code is contributed by phasing17 |
Java
// Java program to check if binary // representations of two numbers are anagrams. import java.util.*; class GFG { // Check each bit in a number is set or not // and return the total count of the set bits. public static int countSetBits( int n) { int count = 0 ; while (n != 0 ) { count += n & 1 ; n >>= 1 ; } return count; } public static boolean areAnagrams( int A, int B) { return countSetBits(A) == countSetBits(B); } // Driver code public static void main(String[] args) { int a = 8 ; int b = 4 ; System.out.println(areAnagrams(a, b)); } } // This code is contributed by phasing17 |
Python3
# Python3 program to check if binary # representations of two numbers are anagrams. # Check each bit in a number is set or not # and return the total count of the set bits. def countSetBits(n) : count = 0 while n> 0 : count + = n & 1 n >> = 1 return count def areAnagrams(A, B) : return countSetBits(A) = = countSetBits(B) # Driver code if __name__ = = "__main__" : a,b = 8 , 4 if areAnagrams(a, b) : print ( "1" ) else : print ( "0" ) # this code is contributed by aditya942003patil |
C#
// C# program to check if binary // representations of two numbers are anagrams. using System; public static class GFG { // Check each bit in a number is set or not // and return the total count of the set bits. public static int countSetBits( int n) { int count = 0; while (n != 0) { count += n & 1; n >>= 1; } return count; } public static bool areAnagrams( int A, int B) { return countSetBits(A) == countSetBits(B); } // Driver code public static void Main() { int a = 8; int b = 4; Console.Write(areAnagrams(a, b)); Console.Write( "\n" ); } } // This code is contributed by Aarti_Rathi |
Javascript
// JavaScript implementation of the above approach // Function to check each bit in a number // and return the total count of set bits function countSetBits(n) { let count = 0; while (n) { count += n & 1; n >>= 1; } return count; } // Function to check if two numbers are anagrams function areAnagrams(A, B) { return countSetBits(A) === countSetBits(B); } // Driver code console.log(areAnagrams(8, 4)); // This code is contributed by Shivam Tiwari |
Output
1
Time Complexity: O (1)
Auxiliary Space: O (1)
Contact Us