[Solution] Monks solution codechef

Monks solution codechef – There is a town with NN people and initially, the ithith person has AiAi coins. However, some people of the town decide to become monks.

Table of Contents

[Solution] Monks solution codechef

If the ithith person becomes a monk, then:

  • He leaves the town thereby reducing the number of people in the town by 11.
  • He distributes XX (0XAi)(0≤X≤Ai) coins to the remaining people of the town (not necessarily equally). Note that each monk can freely choose his value of XX, and different monks may choose different values of XX.
  • He takes the remaining AiXAi−X coins with him.

For example, initially, if A=[1,3,4,5]A=[1,3,4,5] and 4th4th person decides to become a monk then he can leave the town and can give 22 coins to the 1st1st person, 11 coin to the 2nd2nd person, no coins to the 3rd3rd person and take 22 coins along with him while going. Now AA becomes [3,4,4][3,4,4].

Determine 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.

Input Format

  • The first line contains a single integer TT — the number of test cases. Then the test cases follow.
  • The first line of each test case contains an integer NN — the number of people in the town.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN denoting the initial number of coins of everyone in the town.

[Solution] Monks solution codechef

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.

Constraints

  • 1T1051≤T≤105
  • 1N1051≤N≤105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1 

3
4
6 6 6 6
3
5 1 4
5
2 1 2 1 1

Sample Output 1 

0
1
2

[Solution] Monks solution codechef Explanation

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

Test case 22: The 2nd2nd person can become a monk and give his 11 coin to the person with 44 coins. After this, both the remaining people will have 55 coins.

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

  • The 2nd2nd person becomes a monk, and takes his 11 coin with him
  • The 3rd3rd person becomes a monk, and gives one coin each to the 4th4th and 5th5th people

Everyone remaining in the town now has 22 coins.

For Solution

Click Here

Leave a Comment