**Problem Link:** Choose your Fate - Problems - Codechef

**Author:** harshith_4

**Observation and Approach:**

**Case(i):** For every number with all bits set, i.e., for all n, say {2^k} - 1 after every round, the knife will be back at 1 with n>>1 person left till there are 3 people left. And when there are 3 persons left, 1, p, q now 1 kills q and gives the knife to p, p should kill himself => 1 wins.

**Case(ii):** For all *2 powers*, after the first round, the knife gets to 2, and now the situation is similar to case(i) with life at 2. So, similarly, 2 wins.

**Case(iii):** And for every other number, after the first round, it reduces to either case(i) or case(ii), which reduces to 2*(n-p+1) for every n, with p the nearest power of 2 less than n.

**Implementation:** Implementing the above three cases for each number using pre-computed values of complete set bit numbers, i.e., {2^k} - 1 stored in an array.

```
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
const long long MAX = 1e18;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
long long T, n, k, i=2;
cin >> T;
assert(T<=1000);
vector<long long> p = {1};
while(i<=MAX){
p.push_back(i);
i = 2*i+2;
}
while(T--){
cin >> n;
assert(n<=1000);
for(i=0; i<n; i++){
cin >> k;
assert(k<=(long long)1e18);
auto it = upper_bound(p.begin(), p.end(), k) - 1;
if(*it==k-1) cout << 1 << " ";
else if(*it==k) cout << k << " ";
else cout << 2*(k-1-(*it)) << " ";
}
cout << endl;
}
return 0;
}
```

**Submission:** Explanation - Solution - Choose your Fate