### find nth palindrome number

Im doing find nth palindrome number project

let say 12th palindrome number is 12 and 24th palindrome number is 24

 ``12345678910111213141516171819202122`` `````` int n; int count =0; while(true){ cin>> n; if (n == 0) return 0; if( n <= 10000){ for( int i=1 ; i <= 2000000000; i++){ if( palindrom(i) == true) { count++; //cout << "palindrom : " << i<< " count : " << count <

im checking function to check its palindrome or not and increment the count

and if count is equal to number(n) print it.

but if number bigger than 5000 this program take too long.

Im thinking to save the previous value and assign it like this

 ``123456789101112131415161718192021222324`` `````` if(n <=1000 && i==0){ // cout << " here "<1000 && n <=2000 && i==0){ //cout << "there " <2000 && n <=2500 && i==0){ //cout << "there " <2500 && n <=3000 && i==0){ //cout << "there " <

But this help little bit but still take too long and also looks stupid....

is there any method to improve this kind of program?

or any good ideas?
You are doing a brute-force method to validate every number as a palindrome or not.

Try generating palindromic numbers instead. It is possible to take any number palindrome and figure out what the next one is.

Good luck!
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308`` ``````long long jegop(long long a, long long b){ if( b ==0) return 1; long long i,c; c=a; for( i = 0 ; i < b - 1 ; i++ ){ c = c * a; } return c; } void make_vector(vector& vec,long long num){ long long i=1; long long digit; // cout << "begin i : " << i <<" and " << num <= jegop(10,i-1)){ digit = num / jegop(10,i-1); //cout << "push backing..." << digit <& vec){ for(long long i=0; i < vec.size(); i++){ cout << vec[i]; } cout <& vec){ for(long long i=0 ; i < vec.size(); i++){ if( vec[i] == 0 ) return true; } return false; } void increment_pair(vector& vec,long long a, long long b){ vec[a] = vec[a]+1; vec[b] = vec[b]+1; } bool check_All_nine(vector& vec){ for(long long i=0 ; i < vec.size() ; i++){ if( vec[i] != 9) return false; } return true; } void clean(vector& vec){ while( vec.size() !=0){ vec.pop_back(); } } void change_four_digit(vector& vec,long long temp){ //cout << "temp->" << temp <& vec){ long long temp = vec.size(); long long result=0; for(long long i=0 ; i < vec.size() ; i++){ result += vec[i] * jegop(10,temp-1); temp--; } return result; } long long generate_nextPalindrome(vector& vec){ //prlong long(vec); long long mid = vec.size()/2; //cout << "vec_size->" << vec.size() <=9){ // cout <<" one..."< vec; /* while(true){ cin>>num; clean(vec); make_vector(vec,num); cout << "vector size: " << vec.size() <> num; if( num ==0) return 0; result =0; clean(vec); make_vector(vec,1); if( num != 1 && num <=1000000){ for(long long i=1 ; i < num ; i++){ result = generate_nextPalindrome(vec); //cout << "result ::" << result <
I have been tried to write the code to find next palindrome number

i used vector to represent palindrome number and guess next one

11211-> [1,1,2,1,1]

it work much better than last program but still getting slow in certain point

do u have any advice for my code? or other method?
You are doing a few things the hard way. Give me a bit to have the time to profile it and make suggestions -- but I think the single most effective speed update will be to cache some of your results so you don't have to recalculate the entire sequence for each next number.

I found the pattern later and skipping through 10000 dights
(sorry for code i found the pattern while i was writing the code......its little massy)
this work find but question asking to input up to 2*10^9
eventhough i used unsigned long long data type certain point limit exceeded

try to input 200000000

 ``` Else palindrome :8800000001000000088 and 39400000 Else palindrome :8900000001000000098 and 39500000 Else palindrome :9000000001000000009 and 39600000 Else palindrome :9100000001000000019 and 39700000 Else palindrome :9200000001000000029 and 39800000 Else palindrome :9300000001000000039 and 39900000 Else palindrome :9400000001000000049 and 40000000 Else palindrome :9500000001000000059 and 40100000 Else palindrome :9600000001000000069 and 40200000 Else palindrome :9700000001000000079 and 40300000 Else palindrome :9800000001000000089 and 40400000 Else palindrome :9900000001000000099 and 40500000 Else palindrome :10000000011000000001 and 40600000 Else palindrome :11590897989359414786 and 40700000 Else palindrome :17961535885795227607 and 40800000 ```

as u see number limit exceeded in 40700000
I think this was is the maximize the speed of this program.
but i spend almost 24 hours to write this code.......
Do u have better way to solve this problem?
and also how do i solve for this data type limit problem?

first part of code

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145`` ``````#include #include using namespace std; unsigned unsigned long long jegop(unsigned long long a, unsigned long long b){ if( b ==0) return 1; unsigned long long i,c; c=a; for( i = 0 ; i < b - 1 ; i++ ){ c = c * a; } return c; } void make_vector(vector& vec,unsigned long long num){ unsigned long long i=1; unsigned long long digit; // cout << "begin i : " << i <<" and " << num <= jegop(10,i-1)){ digit = num / jegop(10,i-1); //cout << "push backing..." << digit <& vec){ for(unsigned long long i=0; i < vec.size()/2; i++){ cout << vec[i]; } for(unsigned long long i=vec.size()/2; i < vec.size(); i++){ cout << vec[i]; } cout <& vec){ for(unsigned long long i=0 ; i < vec.size(); i++){ if( vec[i] == 0 ) return true; } return false; } void increment_pair(vector& vec,unsigned long long a, unsigned long long b){ vec[a] = vec[a]+1; vec[b] = vec[b]+1; } bool check_All_nine(vector& vec){ for(unsigned long long i=0 ; i < vec.size() ; i++){ if( vec[i] != 9) return false; } return true; } void clean(vector& vec){ while( vec.size() !=0){ vec.pop_back(); } } void change_four_digit(vector& vec,unsigned long long temp){ //cout << "temp->" << temp <& vec){ unsigned long long temp = vec.size(); unsigned long long result=0; for(unsigned long long i=0 ; i < vec.size() ; i++){ result += vec[i] * jegop(10,temp-1); temp--; } return result; } ``````
Last edited on

Second part of code

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258`` `````` unsigned long long generate_nextPalindrome(vector& vec){ //prunsigned long long(vec); unsigned long long mid = vec.size()/2; //cout << "vec_size->" << vec.size() <=9){ // cout <<" one..."<& vec,unsigned long long begin, unsigned long long num, unsigned long long palindrom){ unsigned long long result=0; clean(vec); //cout <<" loading....loading....600000"<< vec.size() <& vec,unsigned long long palindrom){ unsigned long long result=0; clean(vec); make_vector(vec, palindrom); unsigned long long mid = vec.size()/2; unsigned long long begin = 0; unsigned long long end = vec.size()-1; //cout <<" mid : " << mid < 18000000000000000) cout << "exit limit....." <

Last edited on

1st part of main

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193`` ``````int main (int argc, const char * argv[]) { // cout <<"......... "<< jegop(10,9) <<" and " << jegop(10,10) << endl; unsigned long long num=0; unsigned long long result=0; vector temp; /* while(true){ cin>> num; if(num==0) break; cout << generate_100000_palindrom(temp, num)<>num; clean(vec); make_vector(vec,num); cout << "vector size: " << vec.size() < vec; cin >> num; if( num ==0) return 0; result =0; //clean(vec); //make_vector(vec,1); if( num != 1 && num <=250000){ clean(vec); make_vector(vec, 1); for(unsigned long long i=1 ; i < num ; i++){ result = generate_nextPalindrome(vec); //cout << "result ::" << result <250000 && num <=500000 ){ clean(vec); //cout <<" loading....loading...."<< vec.size() <500000 && num <=600000 ){ clean(vec); //cout <<" loading....loading...."<< vec.size() <600000 && num <=700000 ){ clean(vec); //cout <<" loading....loading....700000"<< vec.size() <700000 && num <=800000){ clean(vec); //cout <<" loading....loading....600000"<< vec.size() <800000 && num <=900000){ clean(vec); //cout <<" loading....loading....600000"<< vec.size() <900000 && num <=1000000){ clean(vec); //cout <<" loading....loading....600000"<< vec.size() <1000000 && num <=1100000){ clean(vec); //cout <<" loading....loading....600000"<< vec.size() <1100000 && num <=1200000)result_result(vec,1100000,num,100001100001); else if(num >1200000 && num <=1300000) result_result(vec,1200000,num,200001100002); else if(num >1300000 && num <=1400000) result_result(vec,1300000,num,300001100003); else if(num >1400000 && num <=1500000) result_result(vec,1400000,num,400001100004); else if(num >1500000 && num <=1600000) result_result(vec,1500000,num,500001100005); else if(num >1600000 && num <=1700000) result_result(vec,1600000,num,600001100006);//even else if(num >1700000 && num <=1800000) result_result(vec,1700000,num,700001100007); else if(num >1800000 && num <=1900000) result_result(vec,1800000,num,800001100008); else if(num >1900000 && num <=2000000) result_result(vec,1900000,num,900001100009);//12 else if(num >2000000 && num <=2100000) result_result(vec,2000000,num,1000001000001);//odd 13 else if(num >2100000 && num <=2200000) result_result(vec,2100000,num,1100001000011); else if(num >2200000 && num <=2300000) result_result(vec,2200000,num,1200001000021); else if(num >2300000 && num <=2400000) result_result(vec,2300000,num,1300001000031); else if(num >2400000 && num <=2500000) result_result(vec,2400000,num,1400001000041); else if(num >2500000 && num <=2600000) result_result(vec,2500000,num,1500001000051); else if(num >2600000 && num <=2700000) result_result(vec,2600000,num,1600001000061); else if(num >2700000 && num <=2800000) result_result(vec,2700000,num,1700001000071); else if(num >2800000 && num <=2900000) result_result(vec,2800000,num,1800001000081); else if(num >2900000 && num <=3000000) result_result(vec,2900000,num,1900001000091); else if(num >3000000 && num <=3100000) result_result(vec,3000000,num,2000001000002); else if(num >3100000 && num <=3200000) result_result(vec,3100000,num,2100001000012); ``````

second part of main

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172`` `````` else if(num >3200000 && num <=3300000) result_result(vec,3200000,num,2200001000022); else if(num >3300000 && num <=3400000) result_result(vec,3300000,num,2300001000032); else if(num >3400000 && num <=3500000) result_result(vec,3400000,num,2400001000042); else if(num >3500000 && num <=3600000) result_result(vec,3500000,num,2500001000052); else if(num >3600000 && num <=3700000) result_result(vec,3600000,num,2600001000062); else if(num >3700000 && num <=3800000) result_result(vec,3700000,num,2700001000072); else if(num >3800000 && num <=3900000) result_result(vec,3800000,num,2800001000082); else if(num >3900000 && num <=4000000) result_result(vec,3900000,num,2900001000092); else if(num >4000000 && num <=4100000) result_result(vec,4000000,num,3000001000003); else if(num >4100000 && num <=4200000) result_result(vec,4100000,num,3100001000013); else if(num >4200000 && num <=4300000) result_result(vec,4200000,num,3200001000023); else if(num >4300000 && num <=4400000) result_result(vec,4300000,num,3300001000033); else if(num >4400000 && num <=4500000) result_result(vec,4400000,num,3400001000043); else if(num >4500000 && num <=4600000) result_result(vec,4500000,num,3500001000053); else if(num >4600000 && num <=4700000) result_result(vec,4600000,num,3600001000063); else if(num >4700000 && num <=4800000) result_result(vec,4700000,num,3700001000073); //================================================================================ else if(num >4800000 && num <=4900000) result_result(vec,4800000,num,3800001000083); else if(num >4900000 && num <=5000000) result_result(vec,4900000,num,3900001000093); else if(num >5000000 && num <=5100000) result_result(vec,5000000,num,4000001000004); else if(num >5100000 && num <=5200000) result_result(vec,5100000,num,4100001000014); else if(num >5200000 && num <=5300000) result_result(vec,5200000,num,4200001000024); else if(num >5300000 && num <=5400000) result_result(vec,5300000,num,4300001000034); else if(num >5400000 && num <=5500000) result_result(vec,5400000,num,4400001000044); else if(num >5500000 && num <=5600000) result_result(vec,5500000,num,4500001000054); else if(num >5600000 && num <=5700000) result_result(vec,5600000,num,4600001000064); else if(num >5700000 && num <=5800000) result_result(vec,5700000,num,4700001000074); else if(num >5800000 && num <=5900000) result_result(vec,5800000,num,4800001000084); else if(num >5900000 && num <=6000000) result_result(vec,5900000,num,4900001000094); else if(num >6000000 && num <=6100000) result_result(vec,6000000,num,5000001000005); else if(num >6100000 && num <=6200000) result_result(vec,6100000,num,5100001000015); else if(num >6200000 && num <=6300000) result_result(vec,6200000,num,5200001000025); else if(num >6300000 && num <=6400000) result_result(vec,6300000,num,5300001000035); //else if(num > 6400000 && num) result_result(vec,6400000,num,5300001000035); //5400001000045 if( num > 6400000){ unsigned long long palindrome=5400001000045; for(unsigned long long i=6400000 ; i <= 2*1000000000; i=i+100000){ // cout<< i << endl; //cout << num << " and " << i << endl; if( num > i && num <= i+100000 ){ result_result(vec,i,num,palindrome); cout << "Yes :"<< i <
Er, I'm not going to look through all that...

Yes, there is a definite pattern. I'm not sure but I think you may have noticed that you can generate a palindrome directly from its sequence index.

Another thing that might help is: don't treat it like an atomic number. Treat it as a string of digits. That is, your number is only a palindrome when written as a textual string. So why store it as a number? Store it as a string. Then you can easily generate palindromes like: 9876543210123456789, which is too big for your PC to directly handle as a number.
Holy smokes!
 ``123456789101112131415161718192021222324252627282930313233343536`` ``````pal = [] for i in xrange(0, 10): pal.append(i) for i in xrange(1, 10): pal.append( i * 11 ) for i in xrange(1, 10): pal.append(i * 101) pal.append(i * 111) for i in xrange( 1, 10): pal.append(i * 1001) for ii in xrange(1, 10): pal.append(i * 1001+ii*110) for i in xrange(1, 10): pal.append( i * 10001) for ii in xrange( 1, 10): pal.append(i * 10001 + ii * 100) for ii in xrange(1, 10): pal.append(i * 10001 + ii*1010) for iii in xrange ( 1, 10): pal.append(i * 10001 + ii*1010+ iii* 100) for i in xrange( 1, 10): pal.append(100001 * i) for ii in xrange( 1, 10): pal.append(i * 100001 + 1100 * ii) for ii in xrange( 1, 10): pal.append(i * 100001 + ii * 10010) for iii in xrange( 1, 10): pal.append(i * 100001 + ii * 10010 + iii * 1100) print pal``````

I started this. I was hoping I would be able to come up with a way to generate palindromic numbers directly by studying the pattern. The problem is that every two extra digits I would need to go another level deeper in nested loops. I could keep going until I hit the billions, but it would get more and more tedious.

It's kind of interesting though, the pattern involves multiples of decimal numbers with only 1's and 0's. I bet if you were a genius, you could come up with a way to generate the next palindrome using bitwise operators.
Last edited on
actually i found all the patterns....
there is 10 or more patterns which can represent all the patterns
I'm too tired to write it now.....
this program take me 24 hours .........
i think Duoas advice is helping me
i should use string instead int.
then i don't have to make a vector......
Topic archived. No new replies allowed.