Since log(N^2)=2log(N), the problem becomes easy:
public boolean isPerfectSquare(int num) {
int sqrt=(int)Math.exp(Math.log(num)/2);
return sqrt*sqrt == num || (sqrt+1)*(sqrt+1)==num;
}
I don't think so. While it does state not to use "sqrt" explicitly, it also seems to indicate to not use any built-in library function, which to me would mean any of the math library functions. If you were allowed to do so, you could use power as well:
bool isPerfectSquare(int num) {
return int(pow(num,0.5)) != pow(num, 0.5)? false: true;
}
@adam255 Actually it kind of allows that in a interview, which will enlighten the interviewer that you get quite familiar with the built-in
stuff, quite important portfolio here. But I think the more important here is to solve it in a manual
way, built-in can be a bonus.
Typical binary search method
class Solution {
public:
bool isPerfectSquare(int num)
{
long l = 0, r = num, m = 0;
while(l < r)
{
m = l+(r-l)/2;
if(m*m < num) l = m+1;
else r = m;
}
return r*r==num;
}
};
Using Newton method
class Solution {
public:
bool isPerfectSquare(int num)
{
long g = num;
while(g*g > num) g = (g+num/g)>>1;
return g*g == num;
}
};
B.T.W you guys' solutions are quite original. Awesome, man!