PRPALIN Why am I getting a wrong answer?

general
, ,
1

#include <stdio.h>
#include<conio.h>
int rev(int n)
{
int dig,rev=0;
while(n>0)
{
dig=n%10;
rev=rev*10+dig;
n/=10;
}
return rev;
}

int bins(int pr[],int e)
{int start=0,end=113,mid,flag=0;
while(start<end)
{mid=(start+end)/2;
                if(e>pr[mid])
                {start=mid+1;printf("l");}
                else if(e<pr[mid])
                {end=mid-1;printf("o");}
                else if(e==pr[mid])
                {   flag=1;
                    break;}
}
if (flag==1)
return mid;
else
return 0;
}
void main()
{int j,i,N,revn,count,pr[]={2,3,5,7,11,101,131,151,181,
191,313,353,373,383,727,757,787,797,919,
929,10301,10501,10601,11311,11411,12421,12721,12821,13331,
13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,
17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,
30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,
35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,
39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,
73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,
78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,
94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,
97579,97879,98389,98689,1003001};
scanf("%d",&N);
if(N%2==0)
N--;
for(i=N;;i+=2)
{
revn=rev(i);
if(i==revn)
           {printf("\n%d",revn);
           count=bins(pr,i);
           if(count!=0)
           break;
           }
}
printf("\n%d",i);
getch();
}

Can anyone tell why this code gives wrong output?

2

Dude… At least give us the description of the problem… What do you expect in the output?.. And try to clarify your code to make it a little more readable

2 Likes
3

The problem he/she is trying to solve seems to be PRPALIN: http://www.codechef.com/problems/PRPALIN

3 Likes
4

For example for input 4 it returns:

3oooool
5oooo
5

see http://ideone.com/5GBnce#view_edit_box

1 Like
5

I am assuming that you are trying to solve PRPALIN: http://www.codechef.com/problems/PRPALIN

The logic in bins (binary search) is flawed. This is not a proper binary search. For example, follow the logic when trying to find e=3. It will return 0. It will return 0 for a lot of other palindromic primes as well…

Try to redesign your binary search, and things should improve.

Some details when you submit your program on codechef:

  • main should return an int (0)
  • do not use getch in the program you submit
  • get rid of the extra printfs (“l” and “o” in the binary search, the printf in the loop in main)
  • The \n when printing the result should be after the %d.

You can improve the logic further. Now, you start iterating from N upwards, check to see if the number is a palindrome, and then use the binary search to see if it is prime.

How would you find the result manually if you had the list of palindromic primes and needed to find the smallest palindromic prime larger or equal to some given value N? Try to use that approach in your code.

Good luck.

2 Likes