# Getting WA in Palindrome Number LightOJ

``````// [problem link : https://lightoj.com/problem/palindromic-numbers]

static long[][][][] dp = new long[20][20][2][2];
private static void solve(){
long a = sc.nextLong();
long b = sc.nextLong();
long l = min2(a,b);
long r = max2(a,b);
long ans = helper(r);    // calculate f(r)
if(l<=1)ans --;     // remove edge case when the num created is '0' as considered as a possible solution
else ans -= helper(l-1);
out.println(ans);

}
private static long helper(long n){
int digitLength = (int)(1 + Math.log10(n));
int[] digitArray = new int[digitLength];
for(int i = digitLength-1;i>=0;i--){
digitArray[i] = (int)(n % 10);
n/=10;
}
for(int i=0;i<20;i++)
for(int j=0;j<20;j++)
for(int k=0;k<2;k++)
Arrays.fill(dp[i][j][k],-1);
long ans = memo(0,digitLength-1,0,1,digitArray);
// the edge case when we make a num palindrome > r.
// Like if the r = 10, but we assumed num = 11 as a possible answer, so remove it.
// there is only 1 palindrome that can be created which exceeds r and added by our memo()
for(int i=(digitLength-1)/2; i>=0;i--){
if(digitArray[digitLength-i-1]<digitArray[i]){
ans --;
break;
}
else if(digitArray[digitLength - i - 1]>digitArray[i])break;
}
return ans;
}
// l is the index of left pointer, r is the index of right pointer
// canPlaceZero tells us that whether we can place digit '0' at l and r on both when canPlaceZero = 1.
// if canPlaceZero ==0, it means we haven't created any number yet, so we can not place a '0' at r, so increment l only
// isBound will tell if we are at the boundary of the number
private static long memo(int l, int r,int canPlaceZero,int isBound,int[] digitArray){
if(l>r)return 1;
if(dp[l][r][canPlaceZero][isBound]!=-1)return dp[l][r][canPlaceZero][isBound];
int ans = 0;
int maxDigit = isBound==1?digitArray[l]:9;
for(int digit = 0;digit<=maxDigit;digit++){
if(digit == 0 && canPlaceZero == 0)
ans += memo(l+1,r,0,(isBound==1 && digit == digitArray[l])?1:0,digitArray);
else ans += memo(l+1,r-1,1,(isBound==1 && digit == digitArray[l])?1:0, digitArray);
}
return dp[l][r][canPlaceZero][isBound] = ans;
}``````