New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Distribution of Money

Contributed by

Shrey Pansuria

Last Updated: 23 Feb, 2023

Easy

0/40

Avg time to solve 15 mins

Success Rate 85 %

6 upvotes

Problem Statement

'N' friends are playing together. The wallet balance of each friend is given in an array 'ARR'. In one transaction, a friend who has a wallet balance greater than or equal to Rs. 'K' can give Rs. 'K' to any other friend.

After the transaction, the wallet balance of money taker increases by Rs. 'K', whereas the wallet balance of money giver decreases by Rs. 'K'.

You are given the array containing the wallet balance of each friend and the special number 'K'. Your task is to find the minimum number of transactions needed to make the wallet balance of all the friends the same.

In case if it is not possible to make the wallet balance of all the friends equal, then print -1 in this case.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer, 'T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, 'N' and 'K', denoting the number of elements in the array 'ARR', and the special number respectively.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.

Output Format:

For each test case, print the minimum number of transactions needed to make the wallet balance of all the friends equal.

Print the output of each test case in a new line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
1 <= K <= 10^4
0 <= ARR[i] <= 10^4 

Where 'ARR[i]' represents the ith element of 'ARR'.

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

1
-1

Explanation For Sample Input 1:

For the first test case :  
If Person 4 gives Rs. 2 to Person 1, then the balance of all four persons will be Rs. 6. Hence, the answer is 1 in this case.

For the second test case : 
It is not possible to distribute money equally between friends. Hence, the answer is -1 in this case.

Sample Input 2:

Sample Output 2:

3
0

Explanation For Sample Input 2:

For the first test case :  
If Person 3 gives Rs. 1 to rest all Persons, then the balance of all four persons will be Rs. 4. Hence, the answer is 3 in this case.

For the second test case : 
The money is already equal and so, we dont need to do any further transactions.

Auto

Console