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??
I didnt get the 3*10 factor up there in the count of operations? Also if possible, can you please share the working code?
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
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…
Please accept answer if it’s clear…
Yes. Sure. Thank you so much. Do we have any other approaches other than this ?? Just asking.