Last Updated: 7 Dec, 2020
Check If Binary Representation of a Number is Palindrome
Easy
Asked in companies
Ninja is given an integer ‘N’. Ninja wants to find whether the binary representation of integer ‘N’ is palindrome or not.
A palindrome is a sequence of characters that reads the same backward as forward.
Ninja is busy with his training. Help Ninja in finding out whether the binary representation of ‘N’ is palindrome or not.
Input format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first and only line of each test case contains a single integer ‘N’ denoting the given integer.
Output format:
Return true if the binary representation of the given number is a palindrome. Else return false.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 100
1 <= ‘N’ <= 10^18
Time Limit : 1 sec
Approaches
The main idea is to compare bits from the left and right of the given number. If the i-th from left and right are the same move to the next bit else return false.
Algorithm:-
- Create two variables ‘l’ and ‘r’ and initialize l to 0 and r to log2(N).
- Run a while loop until r > l.
- Check if the l-th bit and r-th bit are the same or not. If both the bits are set or both the bits are unset then it means they are equal and Hence increment l by 1 and decrement r by 1. If they are not equal it means that is not a palindrome. Hence return False.
- In the end, simply return True.