hossainmishkat0's blog

Light OJ 1205
By hossainmishkat0, history, 2 years ago, In English

Any idea on How solve this palindrome problem?? Is this one a dynamic programming problem??!! Light OJ 1205.

https://lightoj.com/problem/palindromic-numbers

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Probably there is a better way than doing binary search (with math) but binary search works fast enough.

It is easy to see that the answer is the number of palindromes from 0 to j minus the number of palindromes from 0 to i, so let's calculate the number of palindromes from 0 to x:

We can split palindromes into the ones with an even number of digits and an odd number of digits and calculate the palindromes independently. We binary search the range we want and for the comparison we consider the palindrome generated with our number, we generate a palindrome with a number by just reversing it and adding to the final of our number, or if it is an odd number of digits palindrome, we remove one of the mid digits, that's it, for example, 127489 -> 127489984721 or 12748984721.

From here on it is trivial.

→ Reply