C++

Forum

 
find nth palindrome number

jake eum (40)
Im doing find nth palindrome number project

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
 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 <<endl;
                
                
                    if( count == n ) {
                    
                        cout << i <<endl;
                   
                        count =0;
                        break;
                    }


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 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 

if(n <=1000 && i==0){
               // cout << " here "<<endl;
                count =0;
                i=0;
               // break;
                
            }else if( n >1000 && n <=2000 && i==0){
                //cout << "there " <<endl;
                count =1000;
                i=90109;
               // break;
            }else if( n >2000 && n <=2500 && i==0){
                //cout << "there " <<endl;
                count =2000;
                i=1001001;
                // break;
            }else if( n >2500 && n <=3000 && i==0){
                //cout << "there " <<endl;
                count =2500;
                i=1501051;
                // break;


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?
Duthomhas (13206)
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!
jake eum (40)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
 
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<long long>& vec,long long num){
    
    
  
    long long i=1;
    long long digit;
   // cout << "begin i : " << i <<" and " << num <<endl;
   // cout <<" vector.size() : " << vec.size() <<endl;
    long long tempNum= num;
    while(true){
        
        if( tempNum <= jegop(10,i)){
           // cout << "breaking..."<<endl;
            break;
        }
           
        else {
            
           // cout << tempNum << " and " << jegop(10,i) << endl;
            i++;
        }
    }
    
    
    
    while(true){
        if (num ==0 ) break;
       
            //cout << " i...." << i <<endl;
            if( num >= jegop(10,i-1)){
                digit = num / jegop(10,i-1);
                //cout << "push backing..." << digit <<endl;
                vec.push_back(digit);
                num = num - (digit * jegop(10,i-1));
                i--;
            }else{
               // cout << "pushing back 0..."<<endl;
                vec.push_back(0);
                i--;
                
                
            }
            
       
    }
    
        
}

void print(vector<long long>& vec){
    for(long long i=0; i < vec.size(); i++){
        
        cout << vec[i]; 
        
    }
    cout <<endl;
}
bool find_zero_inVector(vector<long long>& vec){
    
    for(long long i=0 ; i < vec.size(); i++){
        if( vec[i] == 0 ) return true;
    }
    return false;
}

void increment_pair(vector<long long>& vec,long long a, long long b){
    
    vec[a] = vec[a]+1;
    vec[b] = vec[b]+1;
    
    
}

bool check_All_nine(vector<long long>& vec){
    
    for(long long i=0 ; i < vec.size() ; i++){
        if( vec[i] != 9) return false;
    }
    
    return true;
}

void clean(vector<long long>& vec){
    while( vec.size() !=0){
        
        vec.pop_back();
    }
    
}

void change_four_digit(vector<long long>& vec,long long temp){
    //cout << "temp->" << temp <<endl;
    for(long long i=0 ; i < temp ; i++){
        if( i==0 || i== temp-1) vec.push_back(1);
        else vec.push_back(0);
        
    }
    
    
}

long long vec_to_long(vector<long long>& 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<long long>& vec){
    
    //prlong long(vec);
    long long mid = vec.size()/2;
    //cout << "vec_size->" << vec.size() <<endl;
    if( vec.size()%2 ==1){// if palindrome is odd digits
        //cout << "one...."<<endl;
        long long begin = 0;
        long long end = vec.size()-1;
        while( true ){
            if(( vec[begin] != vec[end]  || begin==end)){
               // cout <<vec[begin] << " AND " << vec[end] <<endl;
                if( vec[begin] <9) {
                  // cout <<" two..."<<endl;
                    //cout << "vec[begin] : " << vec[begin] <<endl;
                    vec[begin] = vec[begin] +1;
                }
                else if( vec[begin]>=9){
                   // cout <<" one..."<<endl;
                    if( check_All_nine(vec)==false){
                       // cout << "begin " << begin <<endl;
                        
                        vec[begin] =0;
                        begin--;
                        end++;
                        while( true){
                            if(vec[begin] !=9 && vec[end] !=9) {
                                //cout <<"fuking..."<<endl;
                                 increment_pair(vec, begin, end);
                                break;
                            }
                            else{
                                
                                vec[begin] =0;
                                vec[end] =0;
                                
                            }
                            begin--;
                            end++;
                        }
                       
                    }else{
                        long long temp = vec.size();
                        clean(vec);
                        change_four_digit(vec,temp+1);
                        
                        
                        
                        
                        
                    }
                    
                    
                }
              
                                
                break;
            }else if(vec[begin] == vec[end] && begin != end){  
                //cout << begin << " and " << end <<endl;
                begin++;
                end--;
            }
            
        }
        
        
    }else if(vec.size()%2 ==0) {// if palindrom is even number 
        //cout <<" two...." <<endl;
        long long begin = 0;
        long long end = vec.size()-1;
        while( true ){
          //  cout << "begin origin: " << begin <<" end origin :  "<< end <<endl;
            if( begin+1 == end){
            
                //cout << "begin : " << begin <<" end :  "<< end <<endl;
                if( vec[begin] !=9 ){
                    
                    //cout << "dkfjslkj..."<<endl;
                    increment_pair(vec,begin,end);
                }else if( vec[begin] ==9 && begin!=0 && check_All_nine(vec)==false){
                   // cout <<"doing...."<<endl;
                    
                    while( true){
                        if(vec[begin] !=9 && vec[end] !=9){
                            //cout << begin << " and " << end <<endl;
                            increment_pair(vec,begin,end);

                            break;
                        }
                        else{
                            
                            vec[begin] =0;
                            vec[end] =0;
                            
                        }
                        begin--;
                        end++;
                    }
                                       
                }else if( check_All_nine(vec)== true){
                    //cout <<"here..."<<endl;
                    long long temp = vec.size();
                    clean(vec);
                    change_four_digit(vec,temp+1);
                    
                    
                    
                    
                }
                
                
                break;
            }
            begin++;
            end--;
        }
        
        
        
        
    }
   // cout <<"Next palindrom :";
    
    //print(vec);
    //cout << " vec_to_long long :  "<< vec_to_long long(vec)<<endl;
    long long re = vec_to_long(vec);
    return re;
}



int main (int argc, const char * argv[])
{    // cout <<"......... "<< jegop(10,9) <<" and " << jegop(10,10) << endl;
    long long num=0;
    long long result=0;
  
    vector<long long> vec;
    /*
    while(true){
        
        cin>>num;
        clean(vec);
        make_vector(vec,num);
        cout << "vector size: " << vec.size() <<endl;
        generate_nextPalindrome(vec);
    }
     
  */
    
    while(true){
        
        cin >> 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 <<endl;
            clean(vec);
            make_vector(vec,result);
            
            
            }
            cout << result <<endl;

        }
        else if( num==1) {
            
        cout << 1 <<endl;
                            
        
    }
jake eum (40)
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?
Duthomhas (13206)
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.
jake eum (40)

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
#include <iostream>
#include <vector>
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<unsigned long long>& vec,unsigned long long num){
    
    
    
    unsigned long long i=1;
    unsigned long long digit;
    // cout << "begin i : " << i <<" and " << num <<endl;
    // cout <<" vector.size() : " << vec.size() <<endl;
    unsigned long long tempNum= num;
    while(true){
        
        if( tempNum <= jegop(10,i)){
            //cout << "breaking..."<<endl;
            break;
        }
        
        else {
            
            //cout << tempNum << " and " << jegop(10,i) << endl;
            i++;
        }
    }
    
    
    
    while(true){
        if (num ==0 ) break;
        
        //cout << " i...." << i <<endl;
        if( num >= jegop(10,i-1)){
            digit = num / jegop(10,i-1);
            //cout << "push backing..." << digit <<endl;
            vec.push_back(digit);
            num = num - (digit * jegop(10,i-1));
            i--;
        }else{
            // cout << "pushing back 0..."<<endl;
            vec.push_back(0);
            i--;
            
            
        }
        
        
    }
    
    
}

void print(vector<unsigned long long>& 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 <<endl;
}
bool find_zero_inVector(vector<unsigned long long>& vec){
    
    for(unsigned long long i=0 ; i < vec.size(); i++){
        if( vec[i] == 0 ) return true;
    }
    return false;
}

void increment_pair(vector<unsigned long long>& vec,unsigned long long a, unsigned long long b){
    
    vec[a] = vec[a]+1;
    vec[b] = vec[b]+1;
    
    
}

bool check_All_nine(vector<unsigned long long>& vec){
    
    for(unsigned long long i=0 ; i < vec.size() ; i++){
        if( vec[i] != 9) return false;
    }
    
    return true;
}

void clean(vector<unsigned long long>& vec){
    while( vec.size() !=0){
        
        vec.pop_back();
    }
    
}

void change_four_digit(vector<unsigned long long>& vec,unsigned long long temp){
    //cout << "temp->" << temp <<endl;
    for(unsigned long long i=0 ; i < temp ; i++){
        if( i==0 || i== temp-1) vec.push_back(1);
        else vec.push_back(0);
        
    }
    
    
}

unsigned long long vec_to_long(vector<unsigned long long>& 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
jake eum (40)


Second part of code


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
 

unsigned long long generate_nextPalindrome(vector<unsigned long long>& vec){
    
    //prunsigned long long(vec);
    unsigned long long mid = vec.size()/2;
    //cout << "vec_size->" << vec.size() <<endl;
    if( vec.size()%2 ==1){// if palindrome is odd digits
        //cout << "one...."<<endl;
        unsigned long long begin = 0;
        unsigned long long end = vec.size()-1;
        while( true ){
            if(( vec[begin] != vec[end]  || begin==end)){
                // cout <<vec[begin] << " AND " << vec[end] <<endl;
                if( vec[begin] <9) {
                    // cout <<" two..."<<endl;
                    //cout << "vec[begin] : " << vec[begin] <<endl;
                    vec[begin] = vec[begin] +1;
                }
                else if( vec[begin]>=9){
                    // cout <<" one..."<<endl;
                    if( check_All_nine(vec)==false){
                        // cout << "begin " << begin <<endl;
                        
                        vec[begin] =0;
                        begin--;
                        end++;
                        while( true){
                            if(vec[begin] !=9 && vec[end] !=9) {
                                //cout <<"fuking..."<<endl;
                                increment_pair(vec, begin, end);
                                break;
                            }
                            else{
                                
                                vec[begin] =0;
                                vec[end] =0;
                                
                            }
                            begin--;
                            end++;
                        }
                        
                    }else{
                        unsigned long long temp = vec.size();
                        clean(vec);
                        change_four_digit(vec,temp+1);
                        
                        
                        
                        
                        
                    }
                    
                    
                }
                
                
                break;
            }else if(vec[begin] == vec[end] && begin != end){  
                //cout << begin << " and " << end <<endl;
                begin++;
                end--;
            }
            
        }
        
        
    }else if(vec.size()%2 ==0) {// if palindrom is even number 
        //cout <<" two...." <<endl;
        unsigned long long begin = 0;
        unsigned long long end = vec.size()-1;
        while( true ){
            //  cout << "begin origin: " << begin <<" end origin :  "<< end <<endl;
            if( begin+1 == end){
                
                //cout << "begin : " << begin <<" end :  "<< end <<endl;
                if( vec[begin] !=9 ){
                    
                    //cout << "dkfjslkj..."<<endl;
                    increment_pair(vec,begin,end);
                }else if( vec[begin] ==9 && begin!=0 && check_All_nine(vec)==false){
                    // cout <<"doing...."<<endl;
                    
                    while( true){
                        if(vec[begin] !=9 && vec[end] !=9){
                            //cout << begin << " and " << end <<endl;
                            increment_pair(vec,begin,end);
                            
                            break;
                        }
                        else{
                            
                            vec[begin] =0;
                            vec[end] =0;
                            
                        }
                        begin--;
                        end++;
                    }
                    
                }else if( check_All_nine(vec)== true){
                    //cout <<"here..."<<endl;
                    unsigned long long temp = vec.size();
                    clean(vec);
                    change_four_digit(vec,temp+1);
                    
                    
                    
                    
                }
                
                
                break;
            }
            begin++;
            end--;
        }
        
        
        
        
    }
   // cout <<"Next palindrom :";
    
   // print(vec);
    //cout << " vec_to_unsigned long long :  "<< vec_to_unsigned long long(vec)<<endl;
    unsigned long long re = vec_to_long(vec);
    return re;
}

void result_result(vector<unsigned long long>& 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() <<endl;
    for(unsigned long long i=begin ; i < num ; i++){
        
        if( i==begin) make_vector(vec, palindrom);
        result = generate_nextPalindrome(vec);
        //cout << "result ::" << result <<endl;
        clean(vec);
        make_vector(vec,result);
        
        
    }
    cout << result <<endl;
    
    
    
    
    
}

unsigned long long generate_100000_palindrom(vector<unsigned long long>& 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 <<endl;
    while(true){
        if( vec.size()%2 ==1){
        
       // cout <<"entered..."<<endl;
       // cout <<"begin..."<< begin <<endl;
       
            //cout<< "loading..." <<endl;
            if( vec[begin+1] != 9 && vec[begin] != 9){
                vec[begin+1] = vec[begin+1]+1;
                vec[end-1] = vec[end-1]+1;
                break;
                
            }else if( vec[begin+1] == 9 && vec[begin] != 9){
                
                vec[begin] = vec[begin]+1;
                vec[begin+1] = 0; 
                
                vec[end] = vec[end]+1;
                vec[end-1] = 0; 
                
                break;
                
                
            }else if( vec[begin+1] == 9 && vec[begin] == 9){
                
                unsigned long long newSize = (vec.size()+2)-1;
               // cout <<"newSize : " <<newSize <<endl;
                clean(vec);
                
                for(unsigned long long i=0; i < newSize; i++){
                    
                    if(i==0 || i ==(newSize/2)-1 || i== newSize-1|| i==(newSize/2)) vec.push_back(1);
                    else vec.push_back(0);
                    
                    
                }
                break;
                
            }else if(vec[begin]==9 && vec[begin+1] !=9){
                
                vec[begin+1]= vec[begin+1]+1;
                vec[end-1] = vec[end-1]+1;
                
                break;
                
                
            }
            
            
        }else{
            
            
            
            if(  vec[begin] != 9){
                vec[begin] = vec[begin]+1;
                vec[end] = vec[end]+1;
                              break;
                
            }else if( vec[begin] ==9){
                
                unsigned long long newSize = (vec.size()+2)-1;
                //cout <<"newSize : " <<newSize <<endl;
                clean(vec);
                
                for(unsigned long long i=0; i < newSize; i++){
                    
                    if(i==0 || i ==newSize/2 || i== newSize-1 ) vec.push_back(1);
                    else vec.push_back(0);
                    
                    
                }
                break;
                
            }
            
            
            
            
            
            
            
            
            
            
        }
        
        
        
    }
        
    if(vec_to_long(vec) > 18000000000000000) cout << "exit limit....." <<endl;
    return vec_to_long(vec);
    
    
    
}

Last edited on
jake eum (40)

1st part of main



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
 
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<unsigned long long> temp;
    /*
    while(true){
        cin>> num;
        if(num==0) break;
    cout << generate_100000_palindrom(temp, num)<<endl;
        
    }*/
    /*
     while(true){
     
     cin>>num;
     clean(vec);
     make_vector(vec,num);
     cout << "vector size: " << vec.size() <<endl;
     generate_nextPalindrome(vec);
     }
     
     */
    
    while(true){
        vector<unsigned long long> 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 <<endl;
                clean(vec);
                make_vector(vec,result);
                
                
            }
            cout << result <<endl;
            
        }
        else if( num==1) {
            
            cout << 1 <<endl;
            
            
        }else if(num >250000 && num <=500000 ){
            clean(vec);
            //cout <<" loading....loading...."<< vec.size() <<endl;
            for(unsigned long long i=250000 ; i < num ; i++){
                
                if( i==250000) make_vector(vec, 15000100051);
                result = generate_nextPalindrome(vec);
                //cout << "result ::" << result <<endl;
                clean(vec);
                make_vector(vec,result);
                
                
            }
            cout << result <<endl;
            
            
        }else if(num >500000 && num <=600000 ){
            clean(vec);
            //cout <<" loading....loading...."<< vec.size() <<endl;
            for(unsigned long long i=500000 ; i < num ; i++){
                
                if( i==500000) make_vector(vec, 40000100004);
                result = generate_nextPalindrome(vec);
                //cout << "result ::" << result <<endl;
                clean(vec);
                make_vector(vec,result);
                
                
            }
            cout << result <<endl;
            
            
        }else if(num >600000 && num <=700000 ){
            clean(vec);
            //cout <<" loading....loading....700000"<< vec.size() <<endl;
            for(unsigned long long i=600000 ; i < num ; i++){
                
                if( i==600000) make_vector(vec, 50000100005);
                result = generate_nextPalindrome(vec);
                //cout << "result ::" << result <<endl;
                clean(vec);
                make_vector(vec,result);
                
                
            }
            cout << result <<endl;
            
            
        }else if(num >700000 && num <=800000){
            clean(vec);
            //cout <<" loading....loading....600000"<< vec.size() <<endl;
            for(unsigned long long i=700000 ; i < num ; i++){
                
                if( i==700000) make_vector(vec, 60000100006);
                result = generate_nextPalindrome(vec);
                //cout << "result ::" << result <<endl;
                clean(vec);
                make_vector(vec,result);
                
                
            }
            cout << result <<endl;
            
            
        }else if(num >800000 && num <=900000){
            clean(vec);
            //cout <<" loading....loading....600000"<< vec.size() <<endl;
            for(unsigned long long i=800000 ; i < num ; i++){
                
                if( i==800000) make_vector(vec, 70000100007);
                result = generate_nextPalindrome(vec);
                //cout << "result ::" << result <<endl;
                clean(vec);
                make_vector(vec,result);
                
                
            }
            cout << result <<endl;
            
            
        }else if(num >900000 && num <=1000000){
            clean(vec);
            //cout <<" loading....loading....600000"<< vec.size() <<endl;
            for(unsigned long long i=900000 ; i < num ; i++){
                
                if( i==900000) make_vector(vec, 80000100008);
                result = generate_nextPalindrome(vec);
                //cout << "result ::" << result <<endl;
                clean(vec);
                make_vector(vec,result);
                
                
            }
            cout << result <<endl;
            
            
        }else if(num >1000000 && num <=1100000){
            clean(vec);
            //cout <<" loading....loading....600000"<< vec.size() <<endl;
            for(unsigned long long i=1000000 ; i < num ; i++){
                
                if( i==1000000) make_vector(vec, 90000100009);
                result = generate_nextPalindrome(vec);
                //cout << "result ::" << result <<endl;
                clean(vec);
                make_vector(vec,result);
                
                
            }
            cout << result <<endl;
            
            
        }else if(num >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);
jake eum (40)

second part of main



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 

 
        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  <<endl;
                    break;
            
                }else {
                    
                    palindrome = generate_100000_palindrom(vec, palindrome);
                    cout << "Else palindrome :" << palindrome << " and " <<  i  <<endl;
                   // cout << "NO"<< endl;
                }
            
            }
        }
        
        //==================================================================================
        
    }
}
Duthomhas (13206)
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.
helios (17574)
Holy smokes!
htirwin (1208)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
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
jake eum (40)
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.