Given an integer can we find if it can be expressed in form of p^q


  • 0
    S

    I am confused as how to approach this problem.
    Any thoughts on this?


  • 1
    Y

    This question is not well defined. I assume you are only interested in integer p and q, and q is greater than 2.
    Otherwise, any integer num=num^1, or num=(num^2)^0.5, etc...

    With that assumption, this is my code to tackle it:

    def func(num):
    for p in range(2, int(num ** 0.5) + 1):
        q = 1
        temp = p
        while temp < num:
            temp *= p
            q += 1
        if temp == num:
            print "Found %d=%d^%d" % (num,p,q)
    

    We simply try every q from 2 to sqrt(num) to check if p can multiply itself exactly to our target number.

    I believe there should be some smarter way to do this. But considering the temp variable in the while loop is increasing exponentially and the outer iteration is restricted to sqrt(num) times, this code actually runs very fast.

    eg:
    func(390625)

    Result:
    Found 390625=5^8
    Found 390625=25^4
    Found 390625=625^2
    [Finished in 0.057s]

    Hope this is what you want.


  • 0
    S

    Thanks.This works perfect. I have tried till n/2 and it takes really long time. Square root is a good catch!


Log in to reply
 

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