C# solution, but getting Time Limit Exceed.


  • 0
    I

    I keep getting time exceed on this with the last case tested at: "1042717401"
    I'm guessing it could be the int -> string / string -> int conversions or perhaps the isPalindrome function?

    How does it work to get a judge to review for whether I should get the credit?

    Solution below

    public class Solution {
        private bool isPalindrome(Int64 target) {
            var s = target.ToString();
            for (int i = 0, j = s.Length - 1; i < j; i++, j--) {
                if ( s[i] != s[j] ) {
                    return false;
                }
            }
            
            return true;
        }
        
        private Int64 getNextPalindrome(Int64 i, Func<Int64, Int64> intFn) {
            Int64 nextInt = intFn(i);
            while ( !isPalindrome( nextInt ) ) {
                nextInt = intFn(nextInt);
            }
            
            return nextInt;
        }
        
        Func<Int64, Int64> upFn = ( i ) => i + 1 ;
        Func<Int64, Int64> downFn = ( i ) => i - 1;
        public string NearestPalindromic(string n) {
            Int64 target = Convert.ToInt64( n );
            
            Int64 upTarget = getNextPalindrome( target, upFn );
            //Console.WriteLine( "Up: " + upTarget );
            Int64 downTarget = getNextPalindrome( target, downFn );
            //Console.WriteLine( "Down: " + downTarget );
            
            Int64 diffUp = Math.Abs( upTarget - target );
            Int64 diffDown = Math.Abs( downTarget - target );
            if ( diffUp == diffDown ) {
                return downTarget.ToString();
            }
            else if ( diffUp < diffDown ) {
                return upTarget.ToString();
            }
            
            return downTarget.ToString();
        }
    }
    

  • 1

    Hi InsomniacFury,

    Sorry, your solution is a brute-force solution, which should not get Accepted.

    There is an non-brute-force solution for this problem, pls take a look. : )


  • 0
    I

    Yes... Yes, I did very much brute-force it. :-(
    Thanks love_Fawn for the context.


Log in to reply
 

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