SPOJ PALIN

From Algorithmist
Jump to: navigation, search

5 - The Next Palindrome[edit]

http://spoj.sphere.pl/problems/PALIN

Summary[edit]

This problem requires us to give the next immediate palindrome after a certain number. Since the constraints of this problem has input sizes of over 1 million digits - brute force and a simple iteration will result in a time limit exceeded (TLE). Instead of having an algorithm based on the input number we need to derive an algorithm that is based on the number of digits within the input. Also obviously we can't work with the built-in data types because they can't store 1 million digits, thus we will operate on a vector/array of integers.

Explanation[edit]

See also the Palindrome article

A careful observation into what a palindrome means gives us a hint to solve the problem. Since a palindrome is effectively "mirrored" around the central digit(s) of a number, we can reflect the first half of the number onto the second half. Keep note that if the number of digits in the number is even - there will be more than one "central" element. So for example, given an input number of say, 1594 - we mirror it to 1551. This number is already a palindrome but obviously it's smaller than the input number so we need to do further work (if it's already larger than, this is the next palindrome after K). Now if we have a palindrome that is less than or equal to the intended number we need to have an algorithm that:

1. Increases the number but maintains it as a palindrome
2. Ensure that we don't skip any palindromes on the way

If we take note that a palindrome must be mirrored, then we can deduce that the next largest palindrome would be one with its central most digit incremented. This can be derived from the fact that the next largest (not necessarily palindrome) number is one with its LSD (least significant digit) increased by 1, however since we need to retain it as a palindrome it also means the MSD will need to be increased also - which is far from optimal. You can observe from this that the most optimal strategy would be to increase the center digits due to the mirror-like property of palindromes. From the example above, if we incremented the first (and consequently last) digit then we yield 2552, however this isn't the most optimal step because you can modify the central digits to 1661 and retain palindrome status.

So we have a basic strategy but it isn't complete. What happens if the center digits happened to be 9's? You set the currently operating digits to be 0 and increment the next pair of digits as this yields the next smallest number. For example, given 1999 - you first mirror it to 1991, increment the center digits to yield 1001 and then increment the next set of digits to yield 2002 - which is the expected answer. This obviously needs to be looped via iteration or called recursively for multiple 9's.

So are we done yet? Not quite. There is still one minor case we need to cover, it's one that reaches to the MSD but still needs to "carry on" the increments or more simply "all 9's". A basic example would be 9999, if you do the algorithm above then you end up yielding 0000 and still need to increment 1 to the next set of digits (which don't exist as of yet). Covering this case is rather simple, add an extra digit '1' to the beginning of the number (i.e. 0000 -> 10000) and change the LSD to a 1 also (for obvious reasons).

Implementations[edit]

Part of the algorithm is implemented below in C++, the work() function basically operates on the processed palindrome. By processed palindrome, we mean that its already mirrored into a palindrome and also has been checked that it is smaller than or equal to the given input number. If the palindrome is already larger than the given input then work() should not be called; otherwise it will return the next palindrome that is larger than the one we are trying to look for. Also pos1 and pos2 respectively refers to the center digit(s). For example, 1661 would have work() be initially called with work(1,2) and 18981 would be initially be called with work(2,2) - note it's a 0-based index.

void work(vector<int>& num, int pos1, int pos2) {
	if (pos1 < 0) {
		num[num.size()-1] = 1;
		num.insert(num.begin(), 1);
		return;
   	} else if (num[pos1] < 9) {
      		num[pos1] = num[pos2] = num[pos1] + 1;
      		return;
   	} else {
     		num[pos1] = num[pos2] = 0;
      		work(num, pos1-1, pos2+1);
      		return;
   	}
}

A simple function that checks whether or not a number is greater than another could look like:

// returns true if v2 is greater than v1, false otherwise
// note: we return false if they are equal because the palindrome we are seeking needs to be strictly greater
bool comp(const vector<int>& v1, const vector<int>& v2) {
	if (v1.size() != v2.size()) 
		return v1.size() < v2.size();
	for (int i = 0; i < v1.size(); i++)
		if (v1[i] != v2[i])
			return v1[i] < v2[i];
	return false;
}

Input[edit]

2
808
2133

Output[edit]

818
2222