## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Monks CodeChef Solution 2022 | Solution CodeChef

## Problem

There is a town with $N$ people and initially, the $i^{th}$ person has $A_i$ coins. However, some people of the town decide to become monks. If the $i^{th}$ person becomes a monk, then:

• He leaves the town thereby reducing the number of people in the town by $1$.
• He distributes $X$ $(0 \le X \le A_i)$ coins to the remaining people of the town (not necessarily equally). Note that each monk can freely choose his value of $X$, and different monks may choose different values of $X$.
• He takes the remaining $A_i - X$ coins with him.

For example, initially, if $A = [1, 3, 4, 5]$ and $4^{th}$ person decides to become a monk then he can leave the town and can give $2$ coins to the $1^{st}$ person, $1$ coin to the $2^{nd}$ person, no coins to the $3^{rd}$ person and take $2$ coins along with him while going. Now $A$ becomes $[3, 4, 4]$.

Determine the minimum number of people who have to become monks, so that in the end, everyone remaining in the

Solution Click Below:-  👉
👇👇👇👇👇

town has an equal number of coins.

### Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — the number of people in the town.
• The second line of each test case contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$ denoting the initial number of coins of everyone in the town.

### Output Format

For each test case, output the minimum number of people who have to become monks, so that in the end, everyone remaining in the town has an equal number of coins.

### Explanation:

Test case $1$: All the people already have an equal number of coins.

Test case $2$: The $2^{nd}$ person can become a monk and give his $1$ coin to the person with $4$ coins. After this, both the remaining people will have $5$ coins.

Test case $3$: One way of two people becoming monks is as follows:

• The $2^{nd}$ person becomes a monk, and takes his $1$ coin with him
• The $3^{rd}$ person becomes a monk, and gives one coin each to the $4^{th}$ and $5^{th}$ people

Everyone remaining in the town now has $2$ coins.