# PROBLEM LINK:

Author: Sahil Chimnani

Tester: Felipe Mota

Editorialist: Rajarshi Basu

# DIFFICULTY:

Easy

# PREREQUISITES:

Implementation, logic, simple math

# PROBLEM:

We have two players who have values JS and TS. We keep dividing them by 2. If at any point one is even and the other is odd, the player corresponding to the even value wins. If both are even, we continue dividing by 2. If both are odd, it’s a tie.

Given player 2’s value, TS \leq 10^{18} find number of JS \leq TS for player 1, such that player 1 wins.

# QUICK EXPLANATION:

Let i be the greatest integer such that 2^i | TS.

ANS = \left \lfloor{\frac{x}{2^{i+1}}}\right \rfloor

# EXPLANATION:

### Subtask 1

For each testcase, iterate over all JS \leq TS and simulate the process.

### Subtask 2

## Observation 1

Any number x can be written as x = 2^{k}*y where 2^k is the highest power of 2 dividing x.

## Implication?

y must be odd

## Observation 2

if 2^k is the

power of 2 that divides TS then 2^{k+1} must be thehighestpower of 2 that divides JS, else player 2 won’t win.minimum

## Just to be clear ...

It does not imply that if JS = 2^{k+1}*y then y is odd. y can be a multiple of 2 as well.

## Full Solution

Find 2^k such that k is the highest power of 2 which divides TS. Divide TS by 2^{k+1} and take the floor. Let that be z. z is the number of possible values of JS.

Relating to the above expressions, we can say that JS = 2^{k+1}*y, and the value of y can be 1,2,3 \dots z such that 2^{k+1}*(z+1) > TS. This is the precise z that we are getting, hence the answer is z. (Since all values from 1 \dots z are possible, hence there are exactly z values.)

## Time Complexity

Since we have to find the maximum 2^i, our time complexity is O(log(TS)) per test case.

# QUICK REMINDERS:

**long long int** is good for your health.

# SOLUTIONS:

## Setter's Code

```
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define db long double
#define pb push_back
#define all(a) a.begin(), a.end()
#define mod 1000000007
#define out cout<<
#define in cin>>
#define w(param) out #param<<" is : "<<param<<"\n"
#define fi first
#define sec second
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vdb vector<db>
#define vbool vector<bool>
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define pll pair<long long,long long>
#define plll pair<long long,pair<long long,long long>>
#define maxn 100005
#define invv(v,from,to) for(int i=from;i<=to;i++) \
in v[i];
#define inv(v) for(int i=0;i<v.size();i++) \
in v[i];
#define printv(v) out #v<<" is :\n"; \
for(int i=0;i<v.size();i++) \
out " "<<v[i];\
nl;
#define printvv(v,from,to) out #v<<" is :\n"; \
for(int i=from;i<=to;i++) \
out " "<<v[i];\
nl;
#define inmax INT_MAX
#define llmax LONG_LONG_MAX
#define nl out "\n"
#define nll out "\n\n"
#define pdd pair<double,double>
using namespace std;
ll g(ll p){
while(p%2 == 0){
p /= 2;
}
p /= 2;
return p;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll q;
in q;
while(q--){
ll ts;
in ts;
out g(ts) << "\n";
}
nl;
return 0;
}
```

## Tester's Code

```
q = int(raw_input())
while q > 0:
ts = int(raw_input())
while ts % 2 == 0:
ts /= 2
print ts / 2
q -= 1
```

Please give me suggestions if anything is unclear so that I can improve. Thanks