Palindromes in both decimal and binary

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 ?

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

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

``````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

even in python i took only 0.495 sec.

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 ?

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…