Multiply by 2, divide by 6 (Codeforces 1374B)
Tags: Math, math

You are given an integer $$$n$$$. In one move, you can either multiply $$$n$$$ by two or divide $$$n$$$ by $$$6$$$ (if it is divisible by $$$6$$$ without the remainder).Your task is to find the minimum number of moves needed to obtain $$$1$$$ from $$$n$$$ or determine if it's impossible to do that.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow. The only line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output: For each test case, print the answer — the minimum number of moves needed to obtain $$$1$$$ from $$$n$$$ if it's possible to do that or -1 if it's impossible to obtain $$$1$$$ from $$$n$$$.

Note: Consider the sixth test case of the example. The answer can be obtained by the following sequence of moves from the given integer $$$15116544$$$:  Divide by $$$6$$$ and get $$$2519424$$$;  divide by $$$6$$$ and get $$$419904$$$;  divide by $$$6$$$ and get $$$69984$$$;  divide by $$$6$$$ and get $$$11664$$$;  multiply by $$$2$$$ and get $$$23328$$$;  divide by $$$6$$$ and get $$$3888$$$;  divide by $$$6$$$ and get $$$648$$$;  divide by $$$6$$$ and get $$$108$$$;  multiply by $$$2$$$ and get $$$216$$$;  divide by $$$6$$$ and get $$$36$$$;  divide by $$$6$$$ and get $$$6$$$;  divide by $$$6$$$ and get $$$1$$$. 

Sample Inputs:
7
1
2
3
12
12345
15116544
387420489

Sample Outputs:
0
-1
2
-1
-1
12
36

Solution (Python):
from sys import stdin, stdout

def prime_factorization(n):
    cnt2 = 0
    cnt3 = 0
    while n % 2 == 0:
        cnt2 += 1
        n //= 2
    while n % 3 == 0:
        cnt3 += 1
        n //= 3
    return (n == 1, cnt2, cnt3)
t = int(stdin.readline().strip())
for _ in range(t):
    n = int(stdin.readline().strip())
    if n == 1:
        stdout.write('0\n')
    else:
        (possible, cnt2, cnt3) = prime_factorization(n)
        if possible and cnt2 <= cnt3:
            stdout.write(str(cnt3 - cnt2 + cnt3) + '\n')
        else:
            stdout.write('-1\n')

Solution (Python):
t = int(input())
ns = []
for _ in range(t):
    ns.append(int(input()))

def func(n):
    san = 0
    er = 0
    while n % 2 == 0:
        er += 1
        n = n // 2
    while n % 3 == 0:
        san += 1
        n = n // 3
    if n != 1:
        return -1
    if er > san:
        return -1
    else:
        return san + (san - er)
for n in ns:
    print(func(n))

Solution (Python):
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inl():
    return map(int, input().split())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())
for t in range(inp()):
    n = inp()
    a = 0
    b = 0
    while n % 2 == 0:
        a += 1
        n //= 2
    while n % 3 == 0:
        b += 1
        n //= 3
    if n != 1 or a - b >= 1:
        print(-1)
    else:
        print(2 * b - a)