# O(1) Java solution

• ``````/*
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;
}``````

• This is obviously O(log_2(num)).

• @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.

• The number of iterations depends on the bit length of the number. Theoretically, it's O(logn) not O(1).

• @jedihy

This looks like a O(1) algorithm. An integer's bit length won't be longer than 32.

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

• @zzhai We should think infinite input!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.