class Solution(object): def isPerfectSquare(self, num): b, e = 1, (num >> 1) + 1 while b <= e: mid = (b + e) >> 1 sq = mid * mid if sq == num: return True if sq > num: e = mid - 1 else: b = mid + 1 return False
This initialization can make it faster:
b = 1 << max(num.bit_length() - 1, 0) / 2 e = 2 * b
Testing a random 100000-bits number, this improved your time (on my PC) from 620 seconds to 207 seconds. (I was curious how it would do after I wrote this solution, which is faster for big numbers.)
So your rationale is that
sqrt(n) cannot be less than half the nearest power of two greater than
n? Can you prove the validity of this assumption?
Also why not
b = (1 << max(num.bit_length() - 1, 0)) >> 1 e = b << 1
It seems like you hate multiplications/divisions :-)
Ts ts ts... shame on you for not knowing the Python operator precedences :-P
/ is stronger than
But to handwavingly prove what I did say: For example for num=40 I get b=1<<(5/2)=4 and e=8. In fact I get b=4, e=8 for num from 16 to 63. And I get b=8, e=16 for num from 64 to 255. My b-formula always jumps to the next higher power of 2 exactly as soon as it can.
If you're referring to my complete lack of multiplications/divisions in my solution... actually I had and preferred
/ 2 and
2*i somewhere and that totally wouldn't have hurt the point I was making, but I wanted to keep the title as it is and it would've been wrong and I didn't want to have to explain why it doesn't matter. (I actually did explain it and then hated it and deleted it.)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.