COME ON CODE ON

A blog about programming and more programming.

Binary Palindromes

with 4 comments

There is this question from a programming competition which requires you to find whether the binary representation of a number is palindrome or not. The input begins with integer T followed by T cases.

The obvious code would be(my solution) :

main(v,r,t,x)
{scanf("%d",&t);while(t--){
for(scanf("%d",&v),x=v,r=0;v;r<<=1,r|=v&1,v>>=1){}
puts(r-x?"NO":"YES");}}

But there were better(shorter) solutions which used recursive main functions :

a,t;main(c,b)
{c?main(c/2,b*2+c%2):
t++/2&&puts(a-b?"NO":"YES"),
~scanf("%d",&a)&&main(a,0);}

-fR0D

Advertisements

Written by fR0DDY

February 13, 2009 at 9:48 AM

Posted in Beautiful Codes

Tagged with

4 Responses

Subscribe to comments with RSS.

  1. A more optimal solution might be not covert complete number in binary. You can easily find out the number of digits in the binary representation and then compare digits at both ends. As soon soon you find any mismatch break;

    This will be very optimized in case large numbers. Won’t have much effect in case of small numbers.

    Also there is a BOUNDARY condition which needs to be checks first that the number should be ODD to be a palindrome.

    ex: 18 = 10010, and we can easily know that it’s just graeter than 2^4 = 16.

    so first compare 18/16 to 18%2 – same
    then (18%16)/8 to (18/2)%2 – diff – HALT

    Akash

    May 19, 2009 at 1:32 PM

  2. Your methods will result in optmizing run-time…while the aim of the contest was to optimize program size….

    fR0D

    May 20, 2009 at 10:12 AM

  3. It wasn’t mentioned in the post…

    Akash

    May 20, 2009 at 2:59 PM

  4. My mistake… 😉

    fR0D

    May 22, 2009 at 10:30 AM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: