Palindromes in both decimal and binary

general
1

Hi everyone,
How to calculate the decimal numbers between [1,N] which are palindromes in both decimal and binary representations. Range of N is [1,10^6]. Time limit is 1 sec.
How to solve this problem ?

2

Why not just iterate and find out?? Because in decimal it’s only 6 digits and in binary it would be just 20 digits at max. It will take less than 1000000 * 3 * 10 operations… which can be solved in c++ in 1sec… no??

2 Likes
3

I didnt get the 3*10 factor up there in the count of operations? Also if possible, can you please share the working code?

4

Here is code and answer:

for i in range(1,1000000):
    num = str(i)
    if(num == num[::-1]):
        binary = ""
        temp = i
        while temp!=0:
            binary += str(temp%2)
            temp/=2

        if binary == binary[::-1]:
            print i

1
3
5
7
9
33
99
313
585
717
7447
9009
15351
32223
39993
53235
53835
73737
585585

1 Like
5

even in python i took only 0.495 sec. :stuck_out_tongue:

6

Thanks mate. Can you please explain the “1000000 * 3 * 10” factor ? 10^6 is for the range of N. Thats understood. What about 3*10 ?

7

Actually that’s just number of comparisons I was talking about… To check if a string is palindrome or not you just have check i th and n-i th element till mid of string… So… But Even 1000000620 would be solvable in 1 sec. because I am checking for palindrome in binary representation only if decimal representation is palindrome… Which reduced calculation very much…

Please accept answer if it’s clear… :slight_smile:

1 Like
8

Yes. Sure. Thank you so much. Do we have any other approaches other than this ?? Just asking.