34 lines
669 B
Python
34 lines
669 B
Python
'''
|
|
You are given an integer n. In one move, you can either: Multiply n by 2, or Divide n by 6 (only if it is divisible by 6 without a remainder).
|
|
Return the minimum number of moves needed to obtain 1 from n, or return -1 if it's impossible to do so.
|
|
|
|
Example 1
|
|
Input:
|
|
1
|
|
Output:
|
|
0
|
|
Example 2
|
|
Input:
|
|
2
|
|
Output:
|
|
-1
|
|
'''
|
|
|
|
class Solution(object):
|
|
def solve(self, n: int) -> int:
|
|
moves = 0
|
|
while n != 1:
|
|
if n % 6 == 0:
|
|
n //= 6
|
|
elif n % 3 == 0:
|
|
n *= 2
|
|
else:
|
|
return -1
|
|
moves += 1
|
|
return moves
|
|
|
|
# Usage
|
|
s = Solution()
|
|
print(s.solve(108))
|
|
|
|
|