perfect_square

2020-11-23.py

import re

question = """

Given a positive integer n, write a function that returns true if 
it is a perfect square and false otherwise. Don’t use any built-in 
math functions like sqrt. Hint: Use binary search!

Examples:
$ perfectSquare(25)
$ true
$ perfectSquare(10) 
$ false

"""

def find_next_digit(r, d):
    for i in range(0,10):
        y = i * (r + i)
        if int(d[0]) >= y:
            continue
        else:
            return(i - 1)
    return 9

def perfectSquare(a):
    answer = []
    z = 0
    b = str(a)
    if len(b) % 2 == 1:
        b = '0' + b
    c = re.compile(r'(\d\d)')
    d = re.findall(c, b)

    l =  len(d)
    r = 0

    for m in range(0,l):
        s = find_next_digit(r, d)
        answer.append(s)
        t = int(d[0]) - ((r + s) * s)
        if (m + 1) < l:
            d[0] = str(t) + d[1]
            d.remove(d[1])
            r = 10 * (r + (2 * s))

    z = "".join([str(elem) for elem in answer])
    if (int(z) * int(z) == a):
        return True
    else:
        return False

print(25, perfectSquare(25))
print(10, perfectSquare(10))