 L_RATING - Editorial

Author: Ram Agrawal
Tester: Ram Agrawal
Editorialist: Ram Agrawal

EASY-MEDIUM

Greedy

PROBLEM:

Yogesh is a very poor guy. He wants to try his luck by buying a lottery ticket. Yogesh is very clever so to increase his chances of winning the lottery he analyzes all the numbers of winning lottery tickets in 1 year and he finds a pattern in the lottery numbers. So he bought some lottery tickets. Each lottery ticket has a number NN on it. He needs to perform some operations on lottery tickets to check whether it is a winning lottery number or not.

Yogesh can run the following operations on a lottery ticket number any number of times.

• he can either multiply it by 2.
• or he can divide it by 6(if it is divisible by 6 without the remainder).

If after performing the following operations any number of times he obtained 1 then it is a winning lottery number.

If it is a winning lottery number print YESYES else print NONO.

Note! - Output is case sensitive "YES" and "Yes" are different.

QUICK EXPLANATION:

If the number consists of other primes than 22 and 33 then the answer is -1. Otherwise, let cnt2cnt2 be the number of twos in the factorization of nn and cnt3cnt3 be the number of threes in the factorization of nn. If cnt2>cnt3cnt2>cnt3 then the answer is -1 because we can’t get rid of all twos. Otherwise, the answer is (cnt3−cnt2)+cnt3(cnt3−cnt2)+cnt3.

Time complexity: O(logn)O(log⁡n).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int cnt2 = 0, cnt3 = 0;
while (n % 2 == 0) {
n /= 2;
++cnt2;
}
while (n % 3 == 0) {
n /= 3;
++cnt3;
}
if (n == 1 && cnt2 <= cnt3) {
cout << 2 * cnt3 - cnt2 << endl;
} else {
cout << -1 << endl;
}
}

return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int cnt2 = 0, cnt3 = 0;
while (n % 2 == 0) {
n /= 2;
++cnt2;
}
while (n % 3 == 0) {
n /= 3;
++cnt3;
}
if (n == 1 && cnt2 <= cnt3) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}

return 0;
}