Блог пользователя Flavius

Number of palindromes less than X
Автор Flavius, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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.

→ Ответить