Python O(50) Solution: Long Division


  • 0

    Algorithm is hard to explain, see the link
    http://www.wikihow.com/Calculate-a-Square-Root-by-Hand
    Basically this algorithm is finding digit by digit, so it will take #digits(10) times half length of number(5/2+2 at most) iterations to find out the solution. The round step is finished by computing sqrt of num*100.

    class Solution(object):
        def mySqrt(self, x):
            if x == 0: return 0
            digs = []
            dig = range(10)[::-1]
            num = x*100
            while num != 0:
                digs.insert(0,num%100)
                num /= 100
            l  = len(digs)
            def att(n,m,res):
                for i in dig:
                    if n >= (20 * m + i) * i:
                        res.append(str(i))
                        return n - (20 * m + i) * i
            res = []
            #print digs
            temp = digs.pop(0)
            for i in dig:
                if temp >= i*i:
                    res.append(str(i))
                    remain = str(temp - i*i)
                    break
            while len(digs) > 0:
                suf = '0' * (2 - len(str(digs[0]))) + str(digs.pop(0))
                n = int(str(remain) + suf)
                m = int(''.join(res))
                remain = str(att(n,m,res))
                #print n,m,remain,digs
            return m
            
            """
            :type x: int
            :rtype: int
            """
    

Log in to reply
 

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