Skip to content

Instantly share code, notes, and snippets.

@jbfeldman
Created November 24, 2020 04:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jbfeldman/1aa84209bab44c14d0566ff5fdc47ea5 to your computer and use it in GitHub Desktop.
Save jbfeldman/1aa84209bab44c14d0566ff5fdc47ea5 to your computer and use it in GitHub Desktop.
Solves @Casidoos 11-23-2020 challenge: find if an integer has a square root
def is_square(n, upper, lower=0):
#edge case
if n == 1:
return True
#if exhausted all possibilities
if upper - lower < 2 and lower**2 != n and upper != n:
return False
guess = ((upper - lower) // 2) + lower
guess_square = guess ** 2
if guess_square == n:
return True
#recurse on lower half
elif guess_square > n:
return is_square(n, upper=guess, lower=lower)
#recurse on higher half
elif guess_square < n:
return is_square(n, upper=upper, lower=guess)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment