7
\$\begingroup\$

I have incremented an integer in the function nextpalin() and converted it into a std::string for finding whether it's a palindrome or not.

If it is a palindrome I return it. The code is giving TLE on SPOJ but working fine on other online IDEs; how to make this code more efficient?

#include <iostream>
#include <string.h>
using namespace std;
int nextpalin (int num){
    while (num++) {
        string str = to_string (num); /// int to string conversion
        int l = str.length()-1;
        int s = 0;
        while( s<l ){
              if (str[s]!=str[l]) break;
              else {
                    s++;
                    l--;
                    }
        if (s>=l) return num;}
                }
   }

int main () {
    int t;
    cin >> t;
    while (t--){
    int num;
    cin >> num;
    if (num==0)  cout << "1" << endl;
   else { 
       if (num<9)  cout << num+1 << endl;
       else  cout << nextpalin( num) << endl;}
     }
}
\$\endgroup\$
9
\$\begingroup\$
  1. Well, my first impression is that your formatting is broken. Generally, before you even consider checking in a new revision to your local source-control or showing it to anyone, the code should be properly formatted, preferably automatically.

  2. Importing big / open-ended namespaces is a bad idea. Read "Why is “using namespace std;” considered bad practice?" for the reasons.

  3. You are missing the header for std::string. The unused header for C-Strings does not make up for that omission.

  4. nextpalin() is quite a non-obvious Abbreviation, nor does it follow any of the conventions for multi-word-names. Why abbreviate at all?

  5. Mark functions and variables only used in the local TU as TU-local using static. That reduces chances for conflicts and encourages inlining.

  6. nextpalin() uses brute-force without any consideration for efficiency. Work smarter not harder, and you might avoid TLE.

  7. Consider using an unsigned type when a negative number makes no sense. Can your input be negative? I doubt it, but you should know better.

  8. Don't arbitrarily restrict the domain of your function without good reason, and document it if you do. Specifically, why doesn't it handle zero, and what business does main() have dealing with it instead?

  9. Always check whether input succeeded. There are any number of ways it could fail.

First, there are smarter ways to check whether a given number is a palindrome in some arbitrary base than conversion to string. See "Palindrome numbers - Project Euler Problem 4". Not that it matters, because incrementing and testing is incredibly inefficient already.

Next, there are smarter ways to go from a number to the next one which is a palindrome than just checking one after the other. One possible algorithm:

  1. n < 0 || n >= max_palindrome => 0
  2. Increment n.
  3. Take the upper half of the number (including middle if odd size).
  4. If it is smaller than the reversed lower half (including middle if odd size), increment it.
  5. Re-generate the bottom half from the top half to get the full number you wanted.

Finding the biggest palindrome, necessary for wrap-around and avoiding overflow:

template <unsigned long long base = 10, class T>
constexpr bool is_power(T n) {
    static_assert(base >= 2, "The base must be at least 2.");
    constexpr T base = BASE;
    if (n > 0)
        while (!(n % base))
            n /= base;
    return n == 1;
}

template <unsigned long long BASE = 10, class T>
constexpr T last_palindrome(T n) {
    static_assert(base >= 2, "The base must be at least 2.");
    constexpr T base = BASE;

    n = n > 0 ? n - 1 : std::numeric_limits<T>::max();
    if (is_power<BASE>(n))
        return n - 1;

    T top = n, rbottom = 0;
    for (; n >= base; n /= base * base) {
        rbottom = rbottom * base + top % base;
        top /= base;
    }
    if (n)
        rbottom = rbottom * base + top % base;

    top -= top > rbottom;

    for (n = n ? top / base : top; n; n /= base)
        top = top * base + n % base;
    return top;
}

An implementation of the algorithm itself:

template <unsigned long long BASE = 10, class T>
constexpr T next_palindrome(T n) {
    static_assert(base >= 2, "The base must be at least 2.");
    constexpr T base = BASE;
    constexpr T biggest = last_palindrome<BASE>(T());

    if (n < 0 || biggest > 0 && n >= biggest)
        return 0;
    ++n;

    T top = n, rbottom = 0;
    for (; n >= base; n /= base * base) {
        rbottom = rbottom * base + top % base;
        top /= base;
    }
    if (n)
        rbottom = rbottom * base + top % base;

    top += top < rbottom;

    for (n = n ? top / base : top; n; n /= base)
        top = top * base + n % base;
    return top;
}
\$\endgroup\$
7
\$\begingroup\$
#include <string.h>

If you want to use C++ string facilities, using <string>. The library <string.h> is a C header and contains functions for working with C strings.


using namespace std;

See Why is using namespace std considered bad practice?.


        while( s<l ){
              if (str[s]!=str[l]) break;
              else {
                    s++;
                    l--;
                    }
        if (s>=l) return num;}
                }

Write code that is consistent and human readable. Avoid situations like that close bracket at the end of the if statement as it can be confusing. Use a formatter like clang-format or astyle if you can't enforce consistency.

Know your <algorithm>s. Your palindrome check is just std::equal over half ranges.


    int t;
    cin >> t;

Always initialize variables with a value.

Check to make sure this read was successful. If not, t could be unmodified (before C++11) or defaulted to 0 (C++11 and later).


    if (num==0)  cout << "1" << endl;

Why does main() care about the input? This check should be in nextpalin().

There are a couple more cases you can rule out.

    if (num < 11) {
        if (num < 0) return 0;
        if (num < 9) return num + 1;
        return 11;
    }

Algorithmically, your approach takes \$O(mn)\$ where \$m\$ is the number of scans and \$n\$ is the number palindromes you check. There is a scanning-only solution \$O(m)\$ that just generates the correct palindrome, exploiting the mirror property of palindromes (that the left half and right half mirror each other).

  • Increment the number by 1 since we are interested in the next palindrome.
  • Compare the two halves (forward scan left, reverse scan right).
    • If left == right: You already found the palindrome so return it.
    • If left > right: The palindrome after a copy would be greater than the previous number. Nothing needed here.
    • If left < right: The palindrome after a copy would be less than the previous number. Increment the left half by 1.
  • Create the palindrome by copying left (forward) to right (reverse).
\$\endgroup\$
  • 1
    \$\begingroup\$ Always initialize variables? Unless, you know, it doesn't matter at all because it will immediately be overwritten. \$\endgroup\$ – Deduplicator Jul 4 '18 at 21:08
  • \$\begingroup\$ And what happens if you use it before it's set? Or use it when you think it's set but actually wasn't? Many of these coding sites still use C++03, meaning std::basic_istream::operator>> still has the behavior "If extraction fails (e.g. if a letter was entered where a digit is expected), value is left unmodified and failbit is set." \$\endgroup\$ – Snowhawk Jul 4 '18 at 21:17
  • \$\begingroup\$ So, the error is not checking whether input failed. I admit to having left out pre-C++11 in my reasoning. \$\endgroup\$ – Deduplicator Jul 4 '18 at 22:00
6
\$\begingroup\$

For starter, since you are doing C++, use C++ headers instead of C ones. And also don't get into the habit of using namespace std. You're typing 20 characters anyway to help you save typing 40. This doesn't feel worth it.

Second, why converting to string when simple arithmetic (division and modulus) allow you to extract single digits as well. to_string would have to do this anyway plus a bunch of other checks and transformations to return the correct string. So you can extract a function testing if a number is palindromic by reversing it using modulus and division.

Lastly, you go to great lengths handling special cases of single digit numbers; but this test should already be done as the outermost while condition in nextpalin. Except you are testing the number you got before incrementing as stopping condition. By using a pre-increment instead of a post-increment, you avoid the need for such special cases.


Proposed improvements:

#include <iostream>


bool isPalindrome (int number) {
    int decomposed = number, reversed = 0;
    while (decomposed) {
        reversed = 10 * reversed + (decomposed % 10);
        decomposed /= 10;
    }
    return reversed == number;
}


int nextPalindromicNumber (int number) {
    while (!isPalindrome(++number));
    return number;
}


int main () {
    int testCases;
    std::cin >> testCases;
    while (testCases--) {
        int number;
        std::cin >> number;
        std::cout << nextPalindromicNumber(number) << '\n';
    }
}
\$\endgroup\$
  • \$\begingroup\$ ,Sir,still you are checking each and every consecutive integer. \$\endgroup\$ – vibhanshu kumar Jul 4 '18 at 21:50
  • 1
    \$\begingroup\$ @vibhanshukumar So are you. I'm building upon your own solution. Others are smarter and provide better approaches, but theses are still improvements. \$\endgroup\$ – Mathias Ettinger Jul 4 '18 at 22:04
  • \$\begingroup\$ @Thanks sir...From my perspective you all are god of this subject... \$\endgroup\$ – vibhanshu kumar Jul 4 '18 at 22:06

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.