+ 4

What is quickest way to determine if a given binary number is a perfect square??

Input is given as string(length N) in binary form(0 & 1) Output will be in form of Yes or No 0<N<100 Ex. 1) Input - 100 Output - Yes Input - 1000000111 Output - No

31st Jan 2019, 5:45 AM
Sudhanshu - avatar
2 Answers
+ 19
● basic way is to convert it from binary to decimal number a & then apply this condition (int)(Math.sqrt(a)*Math.sqrt(a))==a). //I found a fast way to identify if a number is not a square(it will not confirm square number, but it will confirm if a number is not square number) ● if any of 1) or 2) condition becomes false, then number will not be perfect square else number may or may not be perfect square(you have to check by above basic way). 1)check the last digit, it should end with 1,4,5,6,9, 0 (end with even number of zeroes but lets not increase the code lines & steps in it) //if 1) comes true, then move for 2) 2)check for the recursive sum of digits (keep doing sum of digits intil a single number comes) if it is 1,4,7,9 then number may be a square number but if it is not, then it is confirmed it will not be a square number. //so 1) will take very less time in checking for non-square number, after that I have still doubt in 2) & basic way which will be fast & efficient.
17th Mar 2019, 2:51 AM
Gaurav Agrawal
Gaurav Agrawal - avatar
+ 3
In Python it should be: 1 def check(num): 2 print(f"Input - {num}") 3 num = int(num, 2) 4 print(f"Output - {'No' if num**0.5 - int(num**0.5) else 'Yes'}") 5 6 check(input()) 7
31st Jan 2019, 9:27 AM
Pedro Tortello
Pedro Tortello - avatar