online advertising

Saturday, September 6, 2014

SPOJ Problem Set (classical) - The Next Palindrome

Problem:

Please find the problem here.

Solution:

An adhoc problem. The key idea to solve this problem is to try to keep the left hand side as small as possible.

For example, if the input is 1921, we can assert the answer is 1991. To see why, decreasing any digit on the right hand side must also decrease a digit on the left hand side, and with we decrease any digit on the left hand side, the number is less than 1900!

The same apply the number with odd number of digits. Suppose the input is 19321, the same idea apply and the answer is 19391.

So we wanted to flip the left hand side to the right hand side. But unfortunately, sometimes, that doesn't work. Consider the input 1234, 1221 is not an answer, not even 1221 because the problem requires strictly greater. With this example, we also know flipping work if and only if reverse(left) > right.

So what if reverse(left) <= right? In that case we have no choice but to increase the value of the left hand side, minimally so we only plus one. For example, the answer of 1234 will be 1331. For number with even number of digits that is not all 9s, that is a correct solution. To see why, let the number be AB, where A is left part and B is the right part, we also know A reverse(A) <= AB, so the least possible palindrome is (A+1) reverse(A+1). That works if A is not all 9s. If A is all 9s, let say, the number is 9981, than the answer is NOT 100001, but just 10001. 

Last but not least, we also deal with the case with odd number of digits. This time we can increase the middle digit. Suppose the number is AmB, where A is the left part, m is the middle digit, and B is the right part, we also know Am reverse(A) <= AmB, so we have to increase m, if m is not 9. If m is 9, then we have no choice but to increase A, and if A is also all 9s, then we just fall back to the same solution as the all 9s case.

Code:

#include "stdafx.h"

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

#include "PALIN.h"

#include <iostream>
#include <string>

using namespace std;

void processInput(string input)
{
    int length = input.length();
    bool isChainOf9 = true;
    for (unsigned int i = 0; isChainOf9 && i < input.length(); i++)
    {
        if (input[i] != '9') {
            isChainOf9 = false;
        }
    }
    if (isChainOf9)
    {
        cout << 1;
        for (unsigned int i = 0; i < input.length() - 1; i++)
        {
            cout << 0;
        }
        cout << 1;
    }
    else
    {
        int half = length / 2;

        int leftReversePointer = half - 1;      // For example, if length is 4, then leftReversePointer = 1, rightPointer = 2
        int rightPointer = half + length % 2;   // For example, if length is 5, then leftReversePointer = 1, rightPointer = 3
        int leftReverseCompareright = 0;
        while ((leftReverseCompareright == 0) && leftReversePointer >= 0)
        {
            if (input[leftReversePointer] > input[rightPointer])
            {
                leftReverseCompareright = 1;
            }
            else if (input[leftReversePointer] < input[rightPointer])
            {
                leftReverseCompareright = -1;
            }
            leftReversePointer--;
            rightPointer++;
        }

        if (length % 2 == 0)
        {
            if (leftReverseCompareright == 1)
            {
                for (int i = 0; i < half; i++)
                {
                    cout << input[i];                   // For example, 0 to 1
                }
                for (int i = 0; i < half; i++)
                {
                    cout << input[half - 1 - i];        // For example 1 to 0
                }
            }
            else
            {
                int leftLsbPointer = half - 1;
                while (true)
                {
                    if (input[leftLsbPointer] == '9')
                    {
                        input[leftLsbPointer] = '0';
                        leftLsbPointer--;
                    }
                    else
                    {
                        input[leftLsbPointer]++;
                        break;
                    }
                }
                for (int i = 0; i < half; i++)
                {
                    cout << input[i];                   // For example, 0 to 1
                }
                for (int i = 0; i < half; i++)
                {
                    cout << input[half - 1 - i];        // For example 1 to 0
                }
            }
        }
        else
        {
            // Odd length sequences
            char middle = input[length / 2];
            if (leftReverseCompareright == 1)
            {
                for (int i = 0; i < half; i++)
                {
                    cout << input[i];                   // For example, 0 to 1
                }
                cout << middle;
                for (int i = 0; i < half; i++)
                {
                    cout << input[half - 1 - i];             // For example 1 to 0
                }
            }
            else
            {
                if (middle != '9')
                {
                    // 1st, left (middle + 1) reverse(left) is a next palindrome
                    // 2nd, decreasing any digit on the right will decrease digit on the left, so it is no longer a valid next palindrome.
                    // 3rd, decreasing the middle digit it is no longer a valid next palindrome.
                    // 4th, therefore this is the next palindrome
                    for (int i = 0; i < half; i++)
                    {
                        cout << input[i];                   // For example, 0 to 1
                    }
                    cout << (char)(middle + 1);
                    for (int i = 0; i < half; i++)
                    {
                        cout << input[half - 1 - i];             // For example 1 to 0
                    }
                }
                else
                {
                    int leftLsbPointer = half - 1;
                    while (true)
                    {
                        if (input[leftLsbPointer] == '9')
                        {
                            input[leftLsbPointer] = '0';
                            leftLsbPointer--;
                        }
                        else
                        {
                            input[leftLsbPointer]++;
                            break;
                        }
                    }
                    for (int i = 0; i < half; i++)
                    {
                        cout << input[i];                   // For example, 0 to 1
                    }
                    cout << 0;
                    for (int i = 0; i < half; i++)
                    {
                        cout << input[half - 1 - i];             // For example 1 to 0
                    }
                }
            }
        }
    }
    cout << endl;
}

int PALIN()
{
    int round;
    cin >> round;
    for (int roundCount = 0; roundCount < round; roundCount++)
    {
        string input;
        cin >> input;
        processInput(input);
    }

    return 0;
}

No comments :

Post a Comment