QAPT - Editorial

PROBLEM LINK:

Contest

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.

  1. Divide by 2 if it is power of 2.
  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;
}
2 Likes