# PROBLEM LINK:

* Author:* Naman Mittal

* Tester:* Naman Mittal, Rahul Sharma

* Editorialist:* Rahul Sharma

# DIFFICULTY:

Simple

# PREREQUISITES:

Observation, bits, bitwise-operation

# PROBLEM:

Given a number N. Folowing operations can be done on it till it becomes 1.

- Divide by 2 if it is power of 2.
- Subtract highest powerof 2 otherwise.

Alice and Bob play alternatively starting with Alice. One who cannot apply any operation looses. Output the winner.

# QUICK EXPLANATION:

Count number of set bits other that rightmost set bit countSet and count number of zeros countZeros left of the right most set bit. Sum them up countOps = countSet + countZeros. If countSet is odd winner is Alice otherwise Bob.

**Brian Kernighan’s Algorithm:** can be used on N-1 to find countOps.

# EXPLANATION:

**Operation 1**. is equivalent to right shifting of the set bit.

**Operation 2**. is equivalent to resetting the leftmost set bit.

Thus to count the number of operations required to reduce given N to 1 we need to count set bits expect rightmost set bit (**Operation 1**) and number of positions required to right shift rightmost set bit so it reaches LSB or number of zeros on left of the rightmost set bit(**Operation 2**). Let count for **Operation1** be countSet and **Operation 2** be countZeros. Let countOps = countSet + countZeros.

Since Alice starts first thus if countOps is odd Alice will win otherwise Bob.

# COMPLEXITIES:

**Time Complexity:** O(log(N)) for each test case.

**Space Complexity:** O(1)

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
int setBits(unsigned long long int n)
{
int count = 0;
while(n)
{
n &= (n-1);
count++;
}
return count;
}
string AliceVsBob(long long int n)
{
if(setBits(n-1) & 1)
return "Alice";
else
return "Bob";
}
int main()
{
long long int n, t;
cin>>t;
while(t--)
{
cin>>n;
cout<<AliceVsBob(n)<<"\n";
}
return 0;
}
```