-
Notifications
You must be signed in to change notification settings - Fork 2
/
1374B - Multiply by 2, divide by 6.cpp
130 lines (100 loc) · 2.09 KB
/
1374B - Multiply by 2, divide by 6.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/*
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=t=2·104) — the number of test cases. Then t test cases follow.
The only line of the test case contains one integer n (1=n=109).
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.
Example
inputCopy
7
1
2
3
12
12345
15116544
387420489
outputCopy
0
-1
2
-1
-1
12
36
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.
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int res = 0;
bool flag = true;
while(n != 1) {
if (n % 6 == 0) {
n /= 6;
} else {
n *= 2;
if (n % 6 != 0) {
flag = false; break;
}
}
res++;
}
flag ? cout << res : cout << -1;
cout << endl;
}
return 0;
}
/*
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int cnt2 = 0, cnt3 = 0;
while(n % 2 == 0) {
cnt2++;
n /= 2;
}
while (n % 3 == 0) {
cnt3++;
n /= 3;
}
if (n != 1 || cnt2 > cnt3) {
cout << -1 << endl;
continue;
} else {
cout << (cnt3 - cnt2) + cnt3<< endl;
}
}
return 0;
}
*/