aman_naughty's blog

By aman_naughty, history, 5 years ago, In English

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.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I have tried analyzing my code

      Analysis by eyeballing? If that's the case, you'll get nowhere even if you have unlimited time.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -20 Vote: I do not like it

    Completely agree man

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it -16 Vote: I do not like it

        chup

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.