# Solution : improved divide and conquer : O(log(number of digit))

• ``````public class Solution {
public int MySqrt(int x) {
var nbDigit = (int)(Math.Floor(Math.Log(x,10))+1);

if(x <= 1){ return x; }

var l = (int)(Math.Pow(10,(nbDigit+1)/2 -1));
var r = l*10;

while(r-l != 1){
var c = l + (r-l)/2;
if(c > x /c ){
r = c;
}
else{
l = c;
}
}

return l;
}
``````

}

Notice the following :
All squares composed of 1 or 2 digit have there root composed of 1 digit
All squares composed of 3 or 4 digit have there root composed of 2 digit
All squares composed of 5 or 6 digit have there root composed of 3 digit
...

We can deduce the starting bracket for the divide and conquer :
left = 10^( (nbDigit+1)/2 -1)
right = left *10

It could be improved doing the smame in base 2 using bit shift operators

• If you apply the library function logarithm, wouldn't that assumeO(number of digit) computation?

• Log is not a linear function so I believe it is still O(log(number of digit)) : a very long number will take proportionally less time than a short one.

You can compare it to O(n) vs O(log(n)) : finding the max in an array vs search in a sorted array

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