How to make code faster to fit it in time limit?

Question

I'm trying to submit this code on spoj https://www.spoj.com/problems/PALIN which is asking to find next smallest palindrome of a given number n, but as this code works, it is slow therefor it exceeds the time limit (2-9 seconds). is there another way to solve this exercise in a faster way?

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

code:

#include <bits/stdc++.h>
using namespace std;

 int main() {
    long long int t,k; string k2,k1;
    cin>>t;
    while(t--){
        cin>>k;k++;
        do{
            k1=to_string(k);
            k2=k1;
            reverse(k1.begin(), k1.end());
            if(k1==k2){cout<<k<<endl;}
            k++;
        }while(k1!=k2);
    }
    return 0;
}

example input:

2
808
2133

example output:

818
2222

It's the same as always with such challenges. You don't need faster code, you need a better algorithm. So, I'd recommend to get back to the drawing board. You can optimize this as much as you want, testing every single number will be too slow at some point. — Lukas-T, Mar 08 '21 at 07:30
If the code "works", but you just need help tweaking it, you should ask on [CodeReview](https://codereview.stackexchange.com) — Remy Lebeau, Mar 08 '21 at 07:32
never but never use [#include ](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — yaodav, Mar 08 '21 at 08:33

score 4 · Accepted Answer · answered Mar 08 '21 at 07:29

4

The most obvious thing to do is to stop copying and reversing the string. Instead, compare the first character to the last character, then the second to the second-to-last, and so on.

Also, why are you using strings at all? Strings are complex and expensive. The operations you are performing can be done entirely on numbers.

Lastly, consider numbers like "473X". None of those can ever be palindromes. You don't have to test all ten of them. If you're going to look at four-digit numbers starting with "47", there's only one that's a palindrome -- so why are you checking all hundred of them?

Before writing code to solve a problem like this, think through the algorithm you're going to use and make sure you don't have any obvious wasted effort.

answered Mar 08 '21 at 07:29

David Schwartz

179,497
17
214
278

Right! I sometimes imagine "How would I solve this problem manually with data written on cardboard?" Then the solution with the least effort usually becomes obvious... – U. W. Mar 08 '21 at 07:56
This is the right approach of course. Just a note about the `string/number` debate: the input can have up to 10^6 digits... – Damien Mar 08 '21 at 08:24
@Damien That pretty much forces use of a string. But then you have to be *very* efficient in your logic. – David Schwartz Mar 08 '21 at 08:35
yeap finally I solved it /but used strings – javier Robertson Mar 09 '21 at 14:29

How to make code faster to fit it in time limit?

1 Answers1