# PROBLEM LINK

# DIFFICULTY

CAKEWALK

# PREREQUISITES

Ad Hoc, Simple Math

# PROBLEM

In the game of Coin Flip there are initially **N** coins on the table. All these coins are either showing **Heads** or **Tails.** Let us say that the coins are arranged in a line, numbered from **1** to **N**.

You have to perform **N** operations in which you flip all the coins from position **1** to **i** in the **i ^{th}** round. You are to report the number of

**Heads**/

**Tails**after all the operations are complete.

# QUICK EXPLANATION

It is easy to see that at the end of the game the coins would be in alternating positions, starting with either **Heads** or **Tails**. Therefore, either

HTHTHTHT...

Or,

THTHTHTH...

Therefore, you can easily deduce the number of **Heads** or **Tails** at the end of the game.

# EXPLANATION

First, let us prove that the situation at the end of the game is indeed, alternating **Heads** and **Tails**.

Each coin is flipped a fixed number of times.

- The first coin has been flipped
**N**times. Once in each round. - The second coin has been flipped
**N-1**times. Once in each round except the first. - And so on…
- The last coin has been flipped
**once**.

We use the following insights,

- A coin flipped
**even number of times**, will show the**same side**, as it did initially. - A coin flipped
**odd number of times**, will show the**opposite side**, of the one it did initially.

Now Let us consider two cases.

## N is even

We can use the following insights,

- All the coins at
**odd positions**will be in their**initial configuration**. - All the coins at
**even positions**will be**opposite**to their initial configuration. - There are as many even positions as there are odd positions.

Hence, no matter what the initial position is

**The number of coins facing Head and Tail are equal.**

Thus, the answer will always be **N/2**, for the query of **Heads** as well as **Tails**.

## N is odd

We can use the following insights,

- All the coins at
**even positions**will be in their**initial configuration**. - All the coins at
**odd positions**will be**opposite**to their initial configuration. - There are
**floor(N/2)**coins in even positions, and**ceil(N/2)**coins in odd positions.

Hence, no matter what the initial position is

**The number of coins that match the initial configuration are equal to floor(N/2).****The number of coins that do not match the initial configuration are equal to ceil(N/2).**

Thus, assuming integer division, the answer will be **N/2**, for the query that matches the initial configuration. Otherwise the answer will be **N/2 + 1**.

This can be summerized as in the code below.

if (N % 2 == 0 || I == Q) print(N/2) else print(N/2 + 1)

# SETTERS SOLUTION

Can be found here.

# TESTERS SOLUTION

Can be found here.