1

I'm an entry level programmer and I usually work on javascript. I'm trying to improve my programming skills, and started working on SPOJ problems. I'm very new to Online programming.

Please have a look at this question

Input

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

Output For each K, output the smallest palindrome larger than K.

Below is my implementation. It is exceeding the given time limit to execute. What could be a better approach towards solving this? Please help.

#include <iostream>
#include <string>

using namespace std;

string getReverse(string str){
    string reversedString = "";
    double i = str.length();
    while(--i >= 0){
        reversedString += str[i];
    }
    return reversedString;
}

string incrementNumber(string str){
    string nextValue = "";
    long stringLength = str.length();
    long i = 0;
    char temp;
    bool isNotIncremented = true;
    int num[stringLength + 1];
    num[0] = 0;
    while (i++ < stringLength){
        temp = str[i - 1];
        num[i] = temp - 48;
    }
    for (i = stringLength; i > 0; i--){
        if (isNotIncremented){
            if ((num[i] + 1) <= 9){
                num[i] = num[i] + 1;
                isNotIncremented = false;
            }
            else{
                num[i] = 0;
            }
        }
        nextValue = ((char)(48 + num[i])) + nextValue;
    }
    if (isNotIncremented){
        nextValue = "1" + nextValue;
    }
    return nextValue;
}

bool isPalindrome(string str){
    return str == getReverse(str);
}

int main() {
    // your code goes here
    int numTestCases;
    bool nextPalindromeNotFound;
    string nextNumber;

    cin >> numTestCases;

    while(numTestCases--){
        string input;
        cin >> input;

        nextPalindromeNotFound = true;

        nextNumber = input;

        while (nextPalindromeNotFound){
            nextNumber = incrementNumber(nextNumber);
            nextPalindromeNotFound = !(isPalindrome(nextNumber));
        }

        cout << nextNumber << endl;
    }
    return 0;
}
Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
Let me Know
  • 19
  • 2
  • Instead of searching the full state space, consider immediately generating the correct palindrome. Hint: if your number has the format 123XYZ, then the answer must be either 123321 or 124421. – danielschemmel Mar 18 '15 at 07:08
  • @gha.st - how do i make sure that it is the next smallest number? – Let me Know Mar 18 '15 at 07:14
  • Giving an algorithm is fairly trivial once you understand what makes a palindrome a palindrome. However, if you fail to see it, just generate the two and test which one fits the answer... – danielschemmel Mar 18 '15 at 07:18
  • Notice that to create a palindrome, you want to make pairs of characters equal. Now from where should you start to make the characters equal? From the corners or from the middle? – Abhishek Bansal Mar 18 '15 at 07:21
  • thanks for the inputs. I will start working in this approach. – Let me Know Mar 18 '15 at 07:34
  • Similar question was already posted: http://stackoverflow.com/questions/7934519/a-better-algorithm-to-find-the-next-palindrome-of-a-number-string – Miljen Mikic Mar 19 '15 at 17:10

0 Answers0