# O(1) time c++ solution inspired by Q_rsqrt

• ``````class Solution {
public:
bool isPerfectSquare(int num) {
if (num < 0) return false;
int root = floorSqrt(num);
return root * root == num;
}

int32_t floorSqrt(int32_t x) {
double y=x; int64_t i=0x5fe6eb50c7b537a9;
y = *(double*)&(i = i-(*(int64_t*)&y)/2);
y = y * (3 - x * y * y) * 0.5;
y = y * (3 - x * y * y) * 0.5;
i = x * y + 1; return i - (i * i > x);
}
};``````

• Very nice. I'm not really familiar with it and wasn't sure about accuracy, but I tested this with all inputs from 1 to INT_MAX and it got all of them correct.

• Yes, it just works. The idea came from Fast Inverse Square Root.

• how did you find the value 'i' ?

• I am very interested to see how you will come to 0x5fe6eb50c7b537a9 during an interview.

• The following code is the fast inverse square root implementation from Quake III Arena, stripped of C preprocessor directives, but including the exact original comment text:

`````` ...
i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
...``````

• @dploop

Thanks above:

The following code is the fast inverse square root implementation from Quake III Arena, stripped of C preprocessor directives, but including the exact original comment text:[5]

float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;

``````x2 = number * 0.5F;
y  = number;
i  = * ( long * ) &y;                       // evil floating point bit level hacking
i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
y  = * ( float * ) &i;
y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
``````

// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

``````return y;
``````

}

• amazing solution

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