Created
August 3, 2015 12:28
-
-
Save viveksyngh/cbd050d2eb1ec3faf4ca to your computer and use it in GitHub Desktop.
Given a positive integer which fits in a 32 bit signed integer, find if it can be expressed as A^P where P > 1 and A > 0. A and P both should be integers.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#Given a positive integer which fits in a 32 bit signed integer, | |
#Find if it can be expressed as A^P where P > 1 and A > 0. A and P both should be integers. | |
def isPower(A): | |
""" | |
Returns True if number can be expressed as A^P where P > 1 and A > 0 | |
:param: A an integer | |
:return: True if it can be expressed as A^P otherwise False | |
""" | |
if A == 1 : | |
return True | |
elif A <= 3: | |
return False | |
for i in range(2, 33) : | |
temp = self.newtonRaphson(i, A) | |
if temp == int(temp) : | |
return True | |
return False | |
def newtonRaphson(k, n): | |
""" | |
Newton Raphson method for finding kth root of an integer n | |
:param: k an integer, n is also an integer | |
:return: kth root of n | |
""" | |
n = float(n) | |
u, s = n, n+1 | |
while u < s: | |
s = u | |
t = (k-1) * s + n / pow(s, k-1) | |
u = t / k | |
return s |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment