C# solution--using numeric-based palindrome versus character-based solution


  • 0
    D

    This took me a while to get, but I figured it out using numerical methods versus arrays.

    There several important keys to consider:

    • MakePalidrome, itself, solves many of the case; however, sometimes it is over and/or under the nearest palindrome. This is pretty cool itself.
    • There are two cases to be considered: 1) Palindromes lesser than the number, and, 2) Palindromes greater than the number. This has already been explained in other discussions (see the java code).
    • Pay close attention to the pivot points. Let's call these the secrets of the Palindromes :-) For example, answer the question, "why, changing the "2" in "121" or "2" in "2233" can find the nearest palindrome?"
    • This solution was converted from a Java solution that was using character arrays. I didn't like how much copying and parsing that was going on so I tried to accomplish the same things using numerical methods.
    • This solution is 100% faster, but that is kind of deceiving. The N here is not large enough to expose the weaknesses of the numerical methods. For example, indexing of a number isn't O(1). MakePalidrome is O(N*logN) and so forth...
    • At any rate, it was fun... Happy Coding..

    /// <summary>
    /// Given an integer n, find the closest integer (not including itself), which is a palindrome.
    /// The 'closest' is defined as absolute difference minimized between two integers.
    /// </summary>
    public class Solution
    {
        const long radix = 10;
    
        //O(N) algorithm for creating a numerical palindrome
        private long MakePalindrome(long value, int length)
        {
            long exp = 1L;
            int mid = length / 2;
            long reverse = 0;
            int i = 0;
    
            //Truncate value
            while (i++ < mid)
            {
                exp *= radix;
            }
            value /= exp;
    
            
            i = 0;
            long temp = value;
    
            //233 ==> 23 + 2
            if (length % 2 == 1)
            {
                temp /= radix;
            }
    
            //Reverse truncated value
            while (i++ < mid)
            {
                reverse *= radix;
                reverse += temp % radix;
                temp /= radix;
            }
    
            value *= exp;
            value += reverse;
    
            return value;
        }
    
        //Digit value is reversed-order
        //(10)==> Digit 1 is 1, Digit 0 is 0
        private int DigitValue(long x, int n)
        {
            long exp = 1;
    
            while (n-- > 0)
            {
                exp *= radix;
            }
    
            x /= exp;
            x %= radix;
    
            return (int)x;
        }
    
        //Digit order is reversed; 10 ==> 1 @ 1 and 0 @ 0
        private long IncrementAtDigitIndex(long value, long source, int nIndex)
        {
            int i = 0;
    
            while(i++ < nIndex)
            {
                value *= radix;
            }
            
            return source + value;
        }
    
        private int Len(long z)
        {
            long exp = radix;
            int i = 1;
            while (exp <= z)
            {
                i++;
                exp *= radix;
            }
            return i;
        }
    
        private long FindHigherPalindrome(long limit)
        {
            int length = Len(limit);
            long result = MakePalindrome(limit, length);
                        
            for (int i = length - 1; i >= 0; i--)
            {
                int left = DigitValue(limit, i);
                int right = DigitValue(result, i);
                if (left  < right)
                {
                    break;
                }
                else if (left > right)
                {
                    int j = length / 2;//digit-order reversed
                    result = IncrementAtDigitIndex(1L, result, j);
                    // make it palindrome again
                    result = MakePalindrome(result, Len(length));
                    break;
                }
            }
            return result;
        }
    
        private long FindLowerPalindrome(long limit)
        {
            int length = Len(limit);
            long result = MakePalindrome(limit, length);
    
            for (int i = length - 1; i >= 0; i--)
            {
                int left = DigitValue(limit, i);
                int right = DigitValue(result, i);
                if (left > right)
                {
                    break;
                }
                else if (left < right)
                {
                    int j = length / 2;//digit-order reversed
                    result = IncrementAtDigitIndex(-1L, result, j);
    
                    if(length == 2 && result < 10)
                    {
                        result = 9;
                        break;
                    }
    
                    // make it palindrome again
                    result = MakePalindrome(result, Len(result));
                    break;
                }
            }
            return result;
        }
    
        public string NearestPalindromic(string n)
        {
            string result=string.Empty;
    
            if (n.Length > 0)
            {
                long number = long.Parse(n);
                long low = FindLowerPalindrome(number - 1L);
                long high = FindHigherPalindrome(number + 1L);
                result = Math.Abs(number - low) > Math.Abs(number - high) ? high.ToString() : low.ToString();
            }
    
            return result;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.