Java: Brute force with binary search (accepted)


  • 0
    G
    My code
    
     public class Solution {
    	
    	String nearestPalindromic(String n)
    	{
    		long x = Long.parseLong(n);
    		return Long.toString(best(bs(x, true), bs(x, false), x));
    	}
    	
    	long best(long a, long b, long x)
    	{
    		long da = Math.abs(x - a);
    		long db = Math.abs(x - b);
    		if(da == db)
    		{
    			return Math.min(a,  b);
    		}
    		return da < db ? a : b;
    	}
    	
    	
    	
    	long bs(long x, boolean isEven)
    	{
    		long left = 0, right = 999999999;
    		
    		while(left + 1 < right)
    		{
    			long m  = (right + left) / 2;
    			long val = reconstruct(m, isEven);
    			if(val == x)
    			{
    				return best(reconstruct(m - 1, isEven), reconstruct(m + 1, isEven), x);
    			}
    			if(val > x)
    			{
    				right  = m;
    			}
    			else
    			{
    				left = m;
    			}
    		}
    		
    		return best(reconstruct(left, isEven), reconstruct(left + 1, isEven), x);
    	}
    
    	long reconstruct(long half, boolean isEven)
    	{
    		long ret = half;
    		if(!isEven)
    		{
    			half = half/10;
    		}
    		while(half != 0)
    		{
    			ret = ret * 10 + half % 10;
    			half = half / 10;
    		}
    		return ret;
    	}
    
    	
    }
    

Log in to reply
 

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