Flavius's blog

Number of palindromes less than X
By Flavius, history, 7 years ago, In English

Hi guys! I've encountered a problem which basically narrows down to finding f(x) fast, where f(x) is the number of palindromes less than X. For argument sake let's say you have to answer q queries about f(x), with q <= 10^6 and x <= 10^9. I've been struggling to find a solution, so any help would be appreciated.

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

Comments Comments (2)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

There might pe an O(Q*log10(n)) solution,but I can only come up with an O(Q*log2n) one. A palindrome of length N is uniquely determined by its first (N+1)/2 digits.So generating the k-th even-length palindrome or odd length palindrome independently isn't so hard.Because of this,you can do 2 binary searches for each query:the largest even length palindrome less than x,and the largest odd length palindrome less than x.

→ Reply
»
7 years ago, # |
  Vote: I like it +32 Vote: I do not like it

You can just precalculate the palindromic numbers less than 10^9 and store them in a vector. These will be less than 2*10^5 as a palindromic number is uniquely represented by its first (N+1)/2 digits.

Then for each query you just need to binary search in the sorted vector.

→ Reply