Check Palindrome
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

Question

Check Palindrome

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

Accepted Answer

Practise data structures and algorithms especially common questions.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

We are using constant space

Time Complexity: O(logn)Explanation:

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))

C++ (g++ 5.4)

/*
  Time Complexity:O(log2(N))
  Space Complexity:O(1)

  where N is the given number.

*/

#include

bool isKthBitSet(long long x, int k)
{
    return ((x & (1LL << (k - 1))) >= 1) ? true : false;
}

bool checkPalindrome(long long N)
{

    int l = 1;
    long long temp = N;

    int r = log2(N) + 1;

    // Using two pointer to check l-th bit and r-th bit.
    while (l < r)
    {
        // If they are not same it means not a pallindrome.
        if (isKthBitSet(N, l++) != isKthBitSet(N, r--))
        {
            return false;
        }
    }
    return true;
}

Java (SE 1.8)

/*
  
    Time Complexity : O(log2(N))
    Space Complexity: O(1)

    where N is the given number.

*/

public class Solution {
    public static boolean isKthBitSet(long x, int k) {
        return ((x & (1L << (k - 1))) >= 1) ? true : false;
    }

    public static boolean checkPalindrome(long N) {
        int l = 1;
        long temp = N;

        int r = (int) (Math.log(N) / Math.log(2)) + 1;

        // Using two pointer to check l-th bit and r-th bit.
        while (l < r) {
            // If they are not same it means not a pallindrome.
            if (isKthBitSet(N, l++) != isKthBitSet(N, r--)) {
                return false;
            }
        }
        return true;
    }

}

Python (3.5)

"""
  Time Complexity:O(log2(N))
  Space Complexity:O(1)

  where N is the given number.

"""

import math

def isKthBitSet(x, k):
    
    
    return True if ((x & (1<< (k - 1))) >= 1) else  False


def checkPalindrome(N):


    l = 1
    temp = N

    r = int(math.log2(N) + 1)

    # Using two pointer to check l-th bit and r-th bit.
    while (l < r):
    
        # If they are not same it means not a pallindrome.
        if (isKthBitSet(N, l) != isKthBitSet(N, r)):
        
            return False
        
        l+=1
        r-=1
    
    return True