FGT - Editorial

Practice

Author: Tejus Kaw
Tester: Tejus Kaw
Editorialist: Aniket Sood

DIFFICULTY:

EASY

PROBLEM:

There are two children playing with numbers, we are given one of the numbers we have to tell the number of values that the second player can use to win. The second player wins when his number is even and another one has an odd number. If vice versa then he loses. If both have odd then it is a draw and if both have even we divide both the numbers by 2.

QUICK EXPLANATION:

Keep on dividing by 2 until the number becomes odd and then divide by 2 those will be the number of valid numbers that we can have for the second player to win.

EXPLANATION:

If the number given N, is odd then all even numbers are valid so, simply N/2 will be the answer.

Now if N is even and is a power of 2 so since we can’t take any number greater than N and every even number less than N will fail so answer will be directly 0.

Now if N is even number but not a power of 2, so we assume N = 2^k * x , so from here we can see that our answer has to be of the form t = 2^k * 2*y and we are given,

t \leq N

So solving this for y we will get the number of valid options:-
ans = x/2
(x is the odd part which we will get by dividing n repetitively by 2 )

SOLUTIONS:

Setter's Solution
T = int(input())

for i in range(T):
    ans = int(input())
    while not ans&1 :
        ans = ans >> 1
    print((ans - 1)>>1)
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define INF 1e15
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
const int mod = 1e9 + 7;
// dont use accumulate or ceil ------------NEVER----------
void solve(){
int n;
cin>>n;
if(n < 3){
	cout<<0<<"\n";
	return ;
}
if(n&1){
	cout<<n/2<<"\n";
	return;
}else{
	if(n && (!(n&(n-1)))){
		cout<<0<<"\n";
	}else{
		while(n%2==0){
			n /= 2;
		}
		cout<<n/2<<"\n";
	}
}
}
int32_t main()
{
//#ifndef ONLINE_JUDGE
//	freopen("input.txt","r", stdin);
//	freopen("output.txt","w",stdout);
//#endif
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin>>t;
while(t--){
	solve();
}
}