Question

Suppose you are given two positive integers, n and m. How would you determine whether n is a power of m?

Answer 1

Check if \(\log_m n\) is an integer

Answer 2

Ah brilliant - I'm so slow, thanks!

Answer 3

Ask yourself: can n be written in the equivalent form m^x, where x is a positive exponent?

Answer 4

Consider below expression :
\[m^a = n\]

Here, \(a\) is called the logarithm of \(n\) relative to the base \(m\). This is the definition of lagarithm.

Answer 5

n=25 is equivalent to 5^2, where 5 is our " m "

Answer 6

Yea, I was looking at this puzzle in a programming context, and it didn't even occur to me to use logs lol

Answer 7

Remember

logarithm = exponent

Answer 8

so whenever you're dealing with exponents/powers, you're also dealing with logarithms

Answer 9

I was thinking of recursively dividing n by m and checking the end result, but logs are much cleaner

Answer 10

If you have a log function implemented in your language, then yeah could use it directly :)

Answer 11

Thanks!

Answer 12

Do you have an easy way to check if the result will be an integer ?

Answer 13

i mean, in ur language

Answer 14

Sec, I'll post the solution in a moment

Answer 15

Okie :)

Answer 16

from math import log
class Solution(object):
def isPowerOfThree(self, n):
try:
return log(n, 3).is_integer()
except ValueError, AttributeError:
return False

hmm this is failing on 243, 3 because the built in log is returning 4.999999999999

Answer 17

Haha, there must be some nice way to get 5 out of 4.999999

Answer 18

Hmm I need to use the Decimal class I guess

Answer 19

I hate when this happens with rounding and what not

Answer 20

it always happens with floating point numbers, has to do with how the computer stores these floats

Answer 21

I think it would be easier to implement your own function by recursively dividing.

Here you would be messign with only integers and don't have to worry about rounding

Answer 22

http://cr.yp.to/papers/powers.pdf

Answer 23

class Solution(object):
def isPowerOfThree(self, n):
if n == 0:
return False
while n % 3 == 0:
n /= 3
return n == 1

Answer 24

I just needed the power of three for the puzzle, was generalizing for other cases lol

Answer 25

Here's another approach lol
class Solution(object):
def isPowerOfThree(self, n):
return n in (3**x for x in range(41))

Answer 26

too slow when n isn't a power of 3

Answer 27

you're assuming the power is between 0 and 41 is it ?

Answer 28

hahah yeah

Answer 29

but this would generate all 41 powers of 3 in case of mismatches whereas the first solution would exit out as soon as it realized it's not a match

Answer 30

You can make it fast by first creating a file with powers of 3, and loading the file in your function

Answer 31

lol yea, anyway we're overthinking this, I'll see if there are other puzzles