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

Автор aman_naughty, история, 5 лет назад, По-английски

I have a problem: Given two numbers in l and r where l<=r and can be as large as 1e18, I want to count the number of palindrome numbers in the range l to r such that they are a square of some palindrome number.

For example, I have L=4 and R=1000

ans = 4 , numbers are 4, 9, 121, 464.

My code:

code

I am getting the wrong answer on this test case

L=92904622 R=232747148

My answer is 3 but the correct answer is 6.

My approach is to generate all palindromes of length at most 10 and then check if their square is also a palindrome.

I am generating palindromes as follows,

For length 1 I have 10 palindromes from 0 to 9 and for length 2 I have 9 palindromes of the form {11, 22,.., 99}.

Now for forming l length palindrome I simply append digits 1 to 9 at the beginning and the end to each of the generated palindromes of length l-2

Can someone point out what am I doing wrong??

Any help is appreciated.

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

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

Auto comment: topic has been updated by aman_naughty (previous revision, new revision, compare).

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

Do you think codeforces is your personal debugging forum?

Have you tried :

  • Writing a brute force and checking on smaller cases?
  • Making sure the numbers generated are actually a palindrome
  • Making sure you are not missing out on any palindromes by writing a brute ?
  • asking on a smaller group ?

If so, there is nothing wrong with writing such blogs but otherwise imagine if everyone started writing blogs like these for every single code they are not able to debug.

PS: Your code gives 0 for [1002001 1002001] , answer is 1.

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

    I have tried analyzing my code but after spending a fruitful amount of time I could not find a mistake in my code and still cannot, that why is it not generating all the palindromes like your test case. Thanks for the help buddy cheers.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится

    Completely agree man

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

      Will you help strange kids repetitively asking you to do their addition/multiplication homework? Won't it waste your time? Or you rather spend time on their h/w than achieving your own goals? See blog author previous blog entries he constantly asks such question, no one here is his personal teacher. Giving someone direct answers is not helping them in anyway.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -16 Проголосовать: не нравится

        chup

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -11 Проголосовать: не нравится

        I am not asking for the complete solution or approach for the problem, I have thought of a logic and it seems correct but being a green guy I don't think I am that good at the implementation of that logic. Now that I am stuck I was wondering someone could help me in my logic of generating palindromes. Thanks mate.

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

          See if I underatand your algo correctly — For l = 3 you are generating palindromes by appending digits 1-9 to palindromes of l=1 but in this way you will never get palindrome like 080.. For l=4 you can never get palindrome like 10801, hence your logic is incorrect.