-2
\$\begingroup\$

Question

Input number of test cases.

Input each test case and output its next palindrome number.

Link: https://www.spoj.com/problems/PALIN/

Language Used: C++14 (gcc 6.3)


My code

#include<iostream>
using namespace std;
int main()
{
    long long int t,rev=0,x,no,f=0;
    cin>>t;
    while(t>0)
    {
        cin>>no;
        no+=1;
        f=0;
        while(f==0)
        {
            x=no;
            rev=0;
            f=0;
        while(x>0)
        {
            rev=(rev*10)+(x%10);
            x/=10;
        }
        if(rev==no)
            {cout<<rev<<endl;f=1;}
        else
            no+=1;
    }
    t-=1;
}
}

This works for small numbers, but doesn't scale very well - online judge fails with "time limit exceeded".

\$\endgroup\$
  • \$\begingroup\$ Time limit exceeded is still a heck of a lot better than code that doesn't work. \$\endgroup\$ – Mast Aug 28 '18 at 16:35
  • 1
    \$\begingroup\$ Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review. Please take a look at the help center. \$\endgroup\$ – Mast Aug 28 '18 at 16:35
  • \$\begingroup\$ Ok I understand @Mast \$\endgroup\$ – suyashsingh234 Aug 28 '18 at 16:37
  • 2
    \$\begingroup\$ For a given positive integer K of not more than 1000000 digits - uh, using int, which can represent composable palindromes of 9 digits in length, isn't going to cut it. \$\endgroup\$ – Snowhawk Aug 28 '18 at 18:48
  • 1
    \$\begingroup\$ @Snowhawk, just saying that there's no int in the code, so that's of less relevance. Ah, I've just seen that the code was changed. \$\endgroup\$ – Toby Speight Aug 30 '18 at 15:18
1
\$\begingroup\$

Avoid using namespace std;

Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

Variable names could be more informative

What do f, t and x represent? I can just about guess that rev is the reverse of something, but the others give me no clue.

Choose data types wisely

The linked problem statement says that the input may have up to one million digits. None of the built-in integer types have such a range, so you may find it easier to represent the number using a string type.

Use a more intelligent algorithm

We don't need to perform a brute-force search. Given the first half of the number, the second half can be constructed to make a palindrome. All we have to do is to determine whether the middle digit (or digit pair, for even-length numbers) needs to be incremented in order for the result to be larger than the input string.

\$\endgroup\$
  • \$\begingroup\$ for example: 45127. How incrementing 1(middle digit) will give palindrome? \$\endgroup\$ – suyashsingh234 Sep 4 '18 at 15:45
  • 1
    \$\begingroup\$ In 45127, replacing the second half with a mirror of the first will give 45154. That's greater than 45127, so no need to increment the middle digit. But with 72145, the constructed reverse is 72127, which is less than the original. That's when we need to increment the middle digit, giving 72227 as the next palindrome. Obviously, we need to carry if the middle digit was 9 (do that before reflecting the initial digits!). \$\endgroup\$ – Toby Speight Sep 4 '18 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.