The Next Palindrome

April 24, 2009 at 3:00 pm 1 comment

This one is really good

http://www.codechef.com/problems/PALIN/

Advertisements

Entry filed under: Puzzles.

Escalator Marbles

1 Comment Add your own

  • 1. narinderberi  |  April 24, 2009 at 3:11 pm

    Involves good logic (at least for me).

    For a given string aBc, we start from extremities and move inwards. Thus we try to equalize a and c, and then move to making B a palindrome. We always try to modify c to make it equal to a since PLACE of a is higher and we want to ensure that we get the just next palindrome. We also use a flag bNeedsPush to note if we definitely need an increment in B since we may have diminished c to make it equal to a. And in that case, we need a push in B for sure.

    Tricky case exists for number like 99, 999 which are already palindromes, so we start with bNeedsPush as true. Similarly consider numbers like 798.

    We modify 798 to 797 with bNeedsPush=1 (since we diminished c – bNeedsPush was already 1 I know). Then we come to tackle 9. 9 cannot be further incremented, so… Here comes phase 2 logic – the reversal. Now we move from inside outwards trying to finding the first non-9 pair and increment it symmetrically (so that it is still a palindrome and we have not played havoc with the good deeds of phase 1). In case we encounter 9 (or 99), we make it 0 (or 00).

    #include
    #include
    #include

    using namespace std;

    void reverseIter(int *numParts, int aIndex, int cIndex)
    {
    int bDone = 0;

    while(aIndex > 0)
    {
    if(numParts[aIndex] != 9)
    {
    numParts[aIndex]++;
    numParts[cIndex]++;

    bDone = 1;
    break;
    }
    else
    {
    numParts[aIndex] = numParts[cIndex] = 0;
    aIndex–;
    cIndex++;
    }
    }

    if(bDone == 0)
    {
    assert(aIndex == 0);

    numParts[aIndex] = 1;
    numParts[cIndex – 1] = 1;
    }
    }

    void nextPalindrome()
    {
    int numTestCases;
    scanf(“%d”, &numTestCases);

    char *strNum = new char[1000001];
    int *numParts = new int[1000001];

    for(int iTestCase = 0; iTestCase < numTestCases; ++iTestCase)
    {
    memset(strNum, 0, 1000001);
    scanf(“%s”, strNum);

    memset(numParts, 0, 1000001);

    int countDigits = strlen(strNum);

    numParts[0] = 0;//special
    for(int iIter = 0; iIter < countDigits; iIter++)
    {
    numParts[iIter + 1] = strNum[iIter] – ‘0’;
    }

    //start and end indices
    int aIndex = 1;
    int cIndex = countDigits;

    //yes, we need a push
    int bNeedsPush = 1;

    while(aIndex numParts[cIndex])
    {
    numParts[cIndex] = numParts[aIndex];
    if(bNeedsPush)
    bNeedsPush = 0;
    }
    else if(numParts[aIndex] < numParts[cIndex])
    {
    numParts[cIndex] = numParts[aIndex];
    bNeedsPush = 1;
    }

    aIndex++;
    cIndex–;
    }

    if(aIndex == cIndex)
    {
    if(bNeedsPush)
    {
    if(numParts[aIndex] numParts[cIndex])
    {
    numParts[cIndex] = numParts[aIndex];
    bNeedsPush = 0;
    }
    else if(numParts[aIndex] <= numParts[cIndex])
    {
    numParts[cIndex] = numParts[aIndex] = numParts[aIndex] + 1;
    bNeedsPush = 0;
    }
    }
    }
    }

    if(bNeedsPush)
    {
    numParts[0] = 1;
    numParts[countDigits] = 1;
    }

    int nextPalinStart = (numParts[0] == 0) ? 1 : 0;

    for(int iDigit = nextPalinStart; iDigit <= countDigits; iDigit++)
    printf(“%d”, numParts[iDigit]);

    printf(“\n”);
    }
    delete []strNum;
    delete []numParts;
    }

    int main()
    {
    nextPalindrome();

    return 0;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Blog Stats

  • 4,036 hits

Recent Comments


%d bloggers like this: