Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python

# Check if the binary representations of two numbers are anagrams

Ravi

### Overview

In this shot, we’re going to check if the binary representations of two given numbers, $x$ and $y$, are anagrams.

For example, if we have an input of $x=18$ and $y=3$, we should get an output of “Yes”. If, on the other hand, we have an input of $x=11$ and $y=15$, we should receive an output of “No”.

### Solution

To solve this problem, we need to count the number of set bits in both the numbers using Kernighan’s Algorithm.

If the number of set bits in both the numbers is equal, then the binary representations of the numbers are anagrams. If these are not equal, then the binary representations of the numbers are not anagrams.

### Code

def Kernighan(n):
cnt = 0
while n != 0 :
cnt += 1
n = n & n-1
return cnt

x = 11
y = 15

set_bit_count_x = Kernighan(x)
set_bit_count_y = Kernighan(y)

if(set_bit_count_x == set_bit_count_y):
print("Binary representation of " + str(x) + " and " + str(y) + " form an anagram")
else:
print("Binary representation of " + str(x) + " and " + str(y) + " don't form an anagram")

### Explanation

• Lines 1–6: We define a function called Kernighan(). Our function takes a number and returns the number of set bits. It does this by unsetting the rightmost set bit until the number is zero.
• Line 11: We obtain the set bit count of x (set_bit_count_x) by invoking Kernighan() and passing x as the parameter.
• Line 12: We obtain the set bit count of y (set_bit_count_y) by invoking Kernighan() and passing y as the parameter.
• Lines 14–17: We print Yes or No depending on whether set_bit_count_x and set_bit_count_y are equal.

RELATED TAGS

python

CONTRIBUTOR

Ravi
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time

Copyright ©2022 Educative, Inc. All rights reserved.