# C++ Square Root Extraction Method (6ms) v.s. Brute-force attack (23 ms)

• (1) Square Root Extraction Method: 6ms

``````class Solution {
public:
int mySqrt(int x) {
int ans = 0;
if(x < 2)
ans = x;
else
{
int bit = ceil(log10(x)); // original digit bit
int n = ceil(ceil(log10(x)) / 2); // sqrt digit bit
int A = x;

vector<int> num(n, 0);
int i = n - 1;
while(i >= 0)
{
int r = A % 100;
A = (A - r) / 100;
num[i] = r;
--i;
}

int r = 0;
int a = 0;
int product = 0;
int sum = 0;
vector<int> sq(n, 0);
for(int i = 0; i < n; ++i)
{
r += num[i];
int b = 0;
for(int j = 0; j <= 10; ++j)
{
if((sum * 10 + j) * j > r)
{
b = j - 1;
break;
}
}
product = (sum * 10 + b) * b;
sum = (sum * 10 + b) + b;

r -= product;
r *= 100;
sq[i] = b;
}

for(int i = 0; i < n; ++i)
{
ans += sq[i] * pow(10, n - i - 1);
}
}
return ans;
}
};
``````

(2) Brute-force attack: 23 ms

``````class Solution {
public:
int mySqrt(int x) {
int ans = 0;
if(x < 2)
ans = x;
else
{
// Brute-force attack: 23 ms
long long r = 0;
long long n = 0;
while(r <= x)
{
++n;
r = n * n;
}
ans = n - 1;
}
return ans;
}
};
``````

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