how to find total number of numbers whose binary representation is palindrome?

Question 1

I solved the spoj problem and code as below:

#include<iostream>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<string>
using namespace std;
int main()
{
  int a,b,t;
  cin>>t;
  while(t--)
  {
     cin>>a>>b;
     int total=0;
     string s="";
     while(a<=b)
     {
       s="";
       for(int i=a;i>0;i=i/2)
       {
         if(i%2)
            s+='1';
         else
            s+='0';
       }
      string s2="",s3="";
      s2=s.substr(0,s.length()/2);
      int k=s.length();
      if(k%2)
        s3=s.substr(s.length()/2+1,s.length());
      else
        s3=s.substr(s.length()/2,s.length());
      reverse(s2.begin(),s2.end());
      if(s2==s3)
      {
         cout<<a<<" ";
         total++;
      }
      a++;
   }
if(!total)
    cout<<"none"<<endl;
}
return 0;
}

Question 2

One possible approach is:

Take the binary representation of the 1st number M.

Find the 1st number greater than M that is palindrome in binary representation:
- For M, keep the left half of bits, the same value, and match the right half of the binary string with the left half.

For example if M is 10110111, the number shall be 10111101

If the resultant number is < M, then increment the left substring by 1 and then match the right substring.

Eg. if M is 10000011, the number shall be 10000001 < M , hence number shall be 10011001.

To find subsequent numbers, increment bits from the middle towards the end.

Question 3

The time limit is very strict on this problem. Even an optimized palindrome generator will probably not work. You likely have to use the formula at OEIS for this given integer sequence.

There is an inversion formula as well. It's given as follows.

Inversion formula: If b>0 is any binary palindrome, then the index n for which a(n)=b is n=palindromicIndexOf(b)=(((5-(-1)^m)/2) + sum_{k=1...floor(m/2)} (floor(b/2^k) mod 2)/2^k))*2^floor(m/2), where m=floor(log_2(b)).

You probably have to take the two given indexes and find the lowest n and highest n from the sequence somehow. Then print out all nth numbers from the sequence within the range (lowest n, highest n). Each query for the nth binary palindromic number is O(1) time so each test case should take O(log(B - A)) time. This is very very low but you need to get the formula working. :)

Good luck implementing the generator formula for this sequence. I tried it and could not get it to work. :( It's quite complicated.

But anyways for reference, I tried using an optimized palindrome generator in Python 2.7.5 and it gave me Time Limit Exceeded. Here is the code if you're interested.

from itertools import product, repeat
from bisect import insort, bisect

def all_binary_sequences_of_length_(n):
    return [''.join(seq) for seq in product('01', repeat=n)]


def main():
    binary_palindromes = [0, 1, 3, 5, 7]
    for n in xrange(1, 15):
        A = all_binary_sequences_of_length_(n)
        for a in A:
            b = a[::-1]
            # Add palindromes of length 2n + 2
            insort(binary_palindromes, int((a+b).join('11'), 2))
            # Add palindromes of length 2n + 3
            insort(binary_palindromes, int((a+'0'+b).join('11'), 2))
            insort(binary_palindromes, int((a+'1'+b).join('11'), 2))

    t = int(raw_input())
    for _ in repeat(0, t):
        a, b = map(int, raw_input().split())
        start = bisect(binary_palindromes, a - 1)
        end = bisect(binary_palindromes, b)
        output = [str(binary_palindromes[i]) for i in xrange(start, end)]
        if len(output) == 0:
            print 'none'
        else:
            print ' '.join(output)


if __name__ == '__main__':
    main()

I realize Python is not a very fast language but the time limit of only 1 second leads me to believe that the only way to solve this is by using the formula in OEIS. :)

Question 4

Python is powerful! Don't make it complicated! Well, it is a bit slow!

for _ in range(input()):
    has = False
    x,y = map(int, raw_input().split())
    for i in range(x,y+1):
        temp = bin(i)
        temp = temp[temp.index('b')+1:]
        if temp[::-1] == temp:
            has = True
            print i,
    if not has:
        print "none"