CODEWITHSUNDEEP
c++performancec++14c++17
javier Robertson
javier Robertson

Reputation: 15

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

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

Upvotes: 0

Views: 156

Answers (1)

David Schwartz
David Schwartz

Reputation: 182819

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.

Upvotes: 4

Related Questions