How to make this code run more faster

[sanddy1911]

#include <stdio.h>
#include <string.h>

#define BOOL short int
#define TRUE 1
#define FALSE 0

#define MAX 1000002
#define PRE c[m-i]
#define NXT c[m+i+tm]

/* t: Number of Cases.
   len: String Length.
   m: Mid of String Length (tm: 1 if even 0 if odd).
   i: Counter.                                      */

char c[MAX];
BOOL increaseIn(int m, short int tm)
{
    int i=-1;
        while(++i<m&&(PRE=='9')) PRE=NXT='0';// if you read the previous code than you know (mid-i= mid+i) and i dont need to conform this so if they are 9 than make them 0 and make sure i does not exceed mid value.
    if(PRE=='9') {// if the i is eqal to mid and still i is 9 than we need to increase one more digit e.g. 999999 will be 1000001
            NXT='0';
            c[0]='1';
            c[m+i+tm+1]='1';
            c[m+i+tm+2]='\0';
            return FALSE;// this return ensure that the while loop will not be execute
    }
    PRE+=1;// if they are not 9 than increase mid-i value by one
    NXT=PRE;// and than copy mid-i to mid+i
    return TRUE; //// this return ensure that the while loop will execute
}
void nextpoli()
{
    int len=strlen(c);
    int m=len/2;
    int i=-1;
    short int tm=0;
    if(!(len&1)) {
            tm=1;
            m--;
    }
    while(++i<m&&(PRE==NXT)); //Count the value of i until both digit are same e.g. 43232566523765 than i value will be 4 because of pre increment.  
    if(PRE>NXT) NXT=PRE; // if pre (mid-i) value is grater than (mid+i) than mid+i = mid-i. e.g. 43732566523265  than 7>2 will exchange and digit will be 43732566523765.  
    else { //otherwise decrease i by 1. and call the function increaseIn.
        --i;
        if(!increaseIn(m, tm)) return ;
    }

    while(i++<=(m+tm)) NXT=PRE;  // Copy remains previous char to next one.e.g. 43732566523765 will be 43732566523734 
}
main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
    scanf("%s",c);
    nextpoli();
    printf("%s\n",c);
}
return 0;
}

Its takes 0.11 sec to execute on SPOJ i want to run it within .03 sec :/

SPOJ Question: http://www.spoj.com/problems/PALIN/

[Catfish666]

It seems to me that your algorithm is needlessly complicated.

SPOJ wrote:

For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output.

So we're given very large numbers in the form of strings.
Basically we must modify each string K we read, such that it becomes a palindrome.
Additionally, our result must be the smallest palindrome larger than K.

My algorithm would be this:

K_saved = K                     // save original K
i = 0
j = strlen(K) - 1

if (strlen(K) % 2 == 0)         // even length case
{
    do
    {
        // if (K[i] != K[j])    // checks can be removed for speed
            K[j] = K[i];

        ++i;
        --j;
    }
    while (i != j-1);
}
else                            // odd length case
{
    while (i != j)
    {
        // if (K[i] != K[j])    // checks can be removed for speed
            K[j] = K[i];

        ++i;
        --j;
    }
}

// now we must treat special cases such as
// 192 -> 191
// bad result because 192 > 191

if (K_saved > K)
    do
    {
        K[i] = next_digit(K[i]);
        K[j] = K[i];
    }
    while (K[i--] == '0' && K[j++] == '0');

// 191 -> 101 -> 202

// next_digit('0') == '1'
// next_digit('1') == '2'
// next_digit('2') == '3'
// ...
// next_digit('8') == '9'
// next_digit('9') == '0'

inline char next_digit(char c)
{
    switch (c)
    {
        case '0': return '1';
        case '1': return '2';
        // ...
        case '9': return '0';
    }
}

If my algorithm is correct, its complexity should be O(n).

Note that I have not tested my algorithm, and it's not refined.
It may explode in certain special cases.

[ne555]

> For instance, the next higher palindromic number for
> 1234567890873xxxxxxxxxxxxx where x is any digit is
> 12345678908744780987654321
Consider 12345678908730000000000000
the next higher palindromic number would be 12345678908733780987654321

[sanddy1911]

@ Catfish666

Suppose of number 49991 by your algo
it will return 50005 whereas it should return 49994.

[sanddy1911]

@ neo555

Suppose of number 49998 by your algo
it will return 49994 whereas it should return 50005.

[Catfish666]

Suppose of number 49991 by your algo
it will return 50005 whereas it should return 49994.

No. It would only do that if 49991 > 49994.

Also, ne555 was responding to a removed post, written by a third person.
The third person gave an algorithm but then he deleted his post (probably because he saw the same mistake that ne555 talks about).

[sanddy1911]

how u can be sure it is > or not

here is your code run it on your PC and check

#include <stdio.h>
#include <string.h>
using namespace std;
char K[1000002];
char K_saved[1000002];

inline char next_digit(char c)
{
    switch (c)
    {
        case '0': return '1';
        case '1': return '2';
        case '3': return '4';
        case '4': return '5';
        case '5': return '6';
        case '6': return '7';
        case '7': return '8';
        case '8': return '9';
        case '9': return '0';
    }
}

void nextpoli(){                     // save original K
int i = 0;
int j = strlen(K) - 1;

if (strlen(K) % 2 == 0)         // even length case
{
    do
    {
         if (K[i] != K[j])    // checks can be removed for speed
            K[j] = K[i];

        ++i;
        --j;
    }
    while (i != j-1);
}
else                            // odd length case
{
    while (i != j)
    {
         if (K[i] != K[j])    // checks can be removed for speed
            K[j] = K[i];

        ++i;
        --j;
    }
}

if (K_saved > K)
    do
    {
        K[i] = next_digit(K[i]);
        K[j] = K[i];
    }while (K[i--] == '0' && K[j++] == '0');
}

main()
{
int t,i;
scanf("%d",&t);
while(t--) {
    scanf("%s",K);
    for(i=0; i<strlen(K); i++)
        K_saved[i] = K[i];
    nextpoli();
    printf("%s\n",K);
}
return 0;
}

[sanddy1911]

and forgot that what if i pressed 99999

[kbw]

You could get rid of those strlen() calls, which are O(n) complexity and called multiple times. You can track the length yourself.

[sanddy1911]

calling strlen() multiple times is not necessary i knew. it only need to call ones that's all isn't it. or do you have any other idea.

[Catfish666]

kbw was probably referring to:

    for(i=0; i<strlen(K); i++)
        K_saved[i] = K[i];

In the for() loop above, strlen() will be called repeatedly, not just once.
Also, you should use strcpy() or memcpy() instead of manual copy.
http://www.cplusplus.com/reference/cstring/strcpy/
http://www.cplusplus.com/reference/cstring/memcpy/

sanddy1911 wrote:

how u can be sure it is > or not

A hackish way relying on ASCII codes being ordered:
http://www.cplusplus.com/reference/cstring/strcmp/
http://www.cplusplus.com/doc/ascii/

sanddy1911 wrote:

and forgot that what if i pressed 99999

Ah yes, that's the special case I had in mind, when I said the algorithm may explode.

A hackish solution would be to keep track of i an j and when they go out of bounds, all you do is remember to print '1' at the beginning and the end of the result.

if (/* i and j went outside K array */)
    printf("1%s1\n", K);
else
    printf("%s\n", K);

[sanddy1911]

Still giving wrong answer i think there is something wrong with (K_saved > K) can you try this yourself

[Catfish666]

Have you used strcpy() to copy from K to K_save?
Have you used strcmp(K_saved, K) > 0 instead of K_saved > K to compare?

[sanddy1911]

oh i just forgot thats why i was thinking how can u be sure that K_saved > K funny. ok this works but what about this 65464415 or 10, 1, there are many special cases which explode your algo.

[kbw]

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

You're only going to have 1000 or so possible values, so why not store all possible palindromes in an array and use a binary search to lookup the required value?

[ne555]

> You're only going to have 1000 or so possible values
¿ah? ¿what are you counting?

[Catfish666]

Indeed my algorithm has flaws, and so creating an "optimized" program out of it soon became a special case hunt. This was made worse by the fact that SPOJ doesn't say what input/output pair failed.

In the end, my accepted program ran in 0.13 so this is probably not the way to go if you want 0.03 or lower.

[sanddy1911]

Ya for each special case you have to modify your algo an in the end it'll be same as mine, I just want to say there is no problem in my algo but there are some other methods which works faster such as if i use gets instead of scanf than time will reduce to .06 sec but it gives wrong answer because gets create some bugs and i can't figure out why the bug occurs :(.
So if there are some other methods and anyone of you knows than please suggest.

[kbw]

> You're only going to have 1000 or so possible values
¿ah? ¿what are you counting?

Although the range is 1 million, the number have to be palindromes so you'll have (I think):
1000 6 digit numbers
1000 5 digit numbers
100 4 digit numbers
100 3 digit numbers
10 2 digit numbers
10 1 digit numbers

That's 2220 numbers. It's less than 2^11. You can search that with a binary search in less that 3ms on modern kit, never mind the 30ms required.

[Catfish666]

@ kbw: how exactly do you calculate that, for example, there are 1000 six digit palindromes?