L_RATING - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

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;
}