/*
use solution from 069  Sqrt(x), compare res * res == num
time: O(16) = O(1), space: O(1)
*/
public boolean solution(int num) {
int root = 0, bit = 1 << 15;
while (bit > 0) {
root = bit;
if (root > num / root) { // if root * root > num
root ^= bit; // set the bit back to 0
}
bit >>= 1;
}
return root * root == num;
}
O(1) Java solution


@jedihy Hi I just did a quick look at this solution I posted long time ago. But I still think it should be O(1), because the while loop always loop 16 times, which does not change with value of num. Please correct me if I made any mistake.

@zzhai If this is O(1), then any algorithms with limited range input should be O(1), which is not definition of BigOh!
