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, xx and yy, are anagrams.

For example, if we have an input of x=18x=18 and y=3y=3, we should get an output of “Yes”. If, on the other hand, we have an input of x=11x=11 and y=15y=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
RELATED COURSES

View all Courses

Keep Exploring