PROBLEM LINK:
Author: Bhushan Khanale
Editorialist: Bhushan Khanale
DIFFICULTY:
EASY
PREREQUISITES:
None.
PROBLEM:
There are K coins on table. K is always being even, exactly half of coins are facing heads up and half are facing tails upwards. There are total N-1 people who swap any of the coin on the table. The data is provided for N-1 coins if the coins are facing heads or tails upwards. The problem is to find if the Nth coin whose data is not provided is facing heads or tails upwards.
QUICK EXPLANATION:
The problem is simple and requires simple understanding of the swapping/flipping of the coins. When a coin is flipped, say it was facing upwards before flipping, after flipping the number of coins facing heads upwards would decrease by 1 and the number of coins facing tails upwards will increase by 1. Using this, we can solve the problem.
EXPLANATION:
The data is provided for N-1 coins. Hence we know how many coins are facing heads and tails upwards. Now, as K is provided always even the number of coins facing heads and tails will be equal initially. To find the facing status of the hidden coin we simply need to find which type of coin is missing from the given data set. For this, we consider few cases:
- There are even number of heads/tails initially.
- There are odd number of heads/tails initially.
Now, we have to consider some sub-cases for it as well.
- If N-1 is even.
- If N-1 is odd.
Now, if N-1 which is the number of swaps, are even then we will check whether the heads/tails will be even or odd. The key point is that if number of heads is even, number of tails would also be even and same applies for odd as well. Hence after calculating the final status of heads/tails being even or odd we get to know that which of the two coins is missing from the configuration. We will build the solution for all cases and output the answer.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.