# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Utkarsh Gupta

Tester: Jakub Safin, Satyam

Editorialist: Pratiyush Mishra

# DIFFICULTY:

1313

# PREREQUISITES:

Bitwise Operations

# PROBLEM:

Alice and Bob are ready to play a new game. Both the players take alternate turns. Alice starts first.

There are N **binary** numbers written on a blackboard.

- Alice, in her turn, erases any 2 numbers from the blackboard and writes the bitwise OR of those 2 numbers on the blackboard.
- Bob, in his turn, erases any 2 numbers from the blackboard and writes the bitwise AND of those 2 numbers on the blackboard.

Note that, after each move, the count of numbers written on the blackboard reduces by 1.

Both players play until a single number remains on the blackboard. Alice wants to **maximise** the remaining number while Bob wants to **minimise** the remaining number. Find the remaining number if both the players play optimally.

# EXPLANATION:

Here we count the number of 1 and 0 written on the blackboard and store it in variables ones and zeroes respectively.

Now we observe that in one move Alice can take a 1 and 0 and remove the 0 from the board by taking bitwise OR while Bob can take a 0 and a 1 and remove the 1 by taking bitwise AND, provided both 1 and 0 exists.

In the end if only 1s exists then the last remaining would also be 1 only and same for 0.

Thus we just need to check the initial number of 1s and 0s and our answer would be based on whichever one is greater.

# TIME COMPLEXITY:

O(N) for each test case.

# SOLUTION:

Editorialistâ€™s Solution

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution