# Python O(50) Solution: Long Division

• 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
"""
``````

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