Find The Largest Palindrome Lesser Than The Given Number 'N' - O(Log(N)) base 10

Problem:
Given a number "N", find out a number "k" such that 'k' is the largest palindrome that is lesser than "N". [Even when given number is a palindrome]
e.g. if N if 64 print 55, if N=320 Print 313.

Analysis & Algorithm:
For our simplicity we will create an integer array from the given number. This array will save each digit as its element.Lets write IsPalindrome method such that it accepts this integer array and determines whether number is already a palindrome.

We need to understand that while we are doing any swap or interchange or modification, resultant number should not go greater than given number itself.

If second half of the array is mirror image of numbers in first half of the array around mid point, then we can say that is a palindrome. Do not even try decreasing the number in a loop and keep checking whether the reduced number is a palindrome. That certainly is a bad approach.

Lets try anther approach where we make second half of the array as the mirror image of first half of array. For this we can copy numbers in the 'i'th position of array into 'array.length -i'th position. This would assure we will get a palindrome number.

But, wait, this would not give what is asked for. We need to find a number which is strictly lesser than given number and the largest of all palindromes under it.

Lets iterate from i=0 to i<=len/2, where len is the number of digits in the given number.

If we handle few cases then we can improve above mentioned solution to work for us:

1. When a[i] > a[len-i], then we cannot simply copy a[len-i] = a[i], this will make the number greater than given number. This case can be handled like subtraction of a larger digit from a smaller digit, where we take the carry from next digit. Similarly when a[i]>a[len-i], we will try to take the carry from the next digit i.e. a[len-i-1]. If that digit is a zero, we will proceed till we get a non zero integer and then carry from it. i.e. reduce that non zero number in the array by 1 and then make all zeros on the way to 9. This is same like in subtraction again. Once this is done we can copy the value a[i] into a[len-i].

2. If a[i]<a[len-i], directly copy a[i] into a[len-i]

3. If the number itself is a palindrome, reduce the number by 1 and apply the same algorithm as above.


If you take care of indexes properly above algorithm should work you in all the cases. C# Code for above explained solution is below. Comment if you have a suggestion or if you find a problem in my approach.


Solution:



        public static void GetLargestPalindromeLesserThan(int[] num)
        {
            int len = num.Length - 1;
            //check if its already a palindrome, then we will alter the number as 1 as given input
            if(isPalindrome(num))
            {
                int k =0;
                while (num[len - k] == 0)
                {
                    num[len - k] = 9; ;
                    k++;
                }
                num[len - k]--;
            }
            for (int i = 0; i <= len / 2; i++)
            {


                if (i != (len - i))
                {
                    if (num[i] > num[len - i])
                    {

                        int k = 1;
                        while (num[len - i - k] == 0 && (len - i - k) != i)
                        {
                            //same as taking a carry and moving it to next digit
                            num[len - i - k] = 9;
                            k++;
                        }
                        num[len - i - k]--;
                        num[len - i] = num[i];
                    }


                    else
                    {
                        num[len - i] = num[i];
                    }
                }
                
            }
            for (int i = 0; i <= len; i++)
            {
                Console.Write(num[i]);
            }
        }


        private static bool isPalindrome(int[] num)
        {
            int len = num.Length - 1;
            for (int i = 0; i < len / 2; i++)
            {
                if (num[i] != num[len - i])
                {
                    return false;
                }
            }
            return true;
        }