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


  • 0
    G
    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


  • 0
    Q

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


  • 0
    G

    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


Log in to reply
 

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