Check If Binary Representation of a Number is Palindrome

Easy

0/40

Average time to solve is 15m

72 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2    
7
10

Sample Output 1:

true
false

Explanation for Sample Output 1:

For the first test case :
The binary representation of 7 is 111. Hence it is a palindrome.

For the second test case:
The binary representation of 10 is 1010. Hence it is not a palindrome.

Sample Input 2:

2    
3
5

Sample Output 2:

true
true

Hint 1

Compare the bits using a method similar to two pointers

Approaches (1)

Approach 1

Bitmasking Approach

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.

Time Complexity

O(log2(N)) where ‘N’ is the given number.

We are iterating over all the bits of N and the total number of bits in ‘N’ is log2(N) +1. Therefore the time complexity is O(log2(N))

Space Complexity

O(1)

We are using constant space

(100% EXP penalty)

Check If Binary Representation of a Number is Palindrome

Console