Distribution of Money
'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.
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
Approach: The idea is to first find the wallet balance of each friend, assuming that the wallet balance of all friends are made the same. As we can see, the summation of the wallet balance of all the friends remains the same after any number of transactions, therefore the wallet balance of each friend, if the wallet balance of all the friends are the same will be equal to the average wallet balance of the 'N' friends.
So our first idea is to check whether the average balance is an integer. If it is not an integer, then we will return -1. As we can transact in integer values only. The other condition to check is that for each friend, the difference of his initial wallet balance and the average wallet balance should be a multiple of ‘K’. If it is not, then we will return -1.Otherwise, it is guaranteed that an answer exists.
This works because we are allowed to transact in multiples of ‘K’ only. This means that the wallet balance of a friend increases or decreases in multiples of 'K' only. Therefore, it is necessary that the difference between initial wallet balance and the average wallet balance of friends is multiple of ‘K’.
To find the transactions, we can iterate through all the friends having an initial balance greater than the average balance and count how many transactions are required for each friend so that their wallet balance becomes exactly equal to the average balance. Our final answer will be the total number of transactions that are carried out.
Algorithm:
- Let ‘BALANCESUM’ denote the sum of the wallet balance of all the friends.
- If ‘BALANCESUM’ is not divisible by ‘K’, then we will return -1.
- Otherwise, we will set ‘AVERAGEBALANCE’ as the quotient of the division of ‘BALANCESUM’ and ‘N’.
- Define the ‘TRANSACTIONCOUNT’ variable to store the total count of transactions. Initialize it as 0.
- Iterate from ‘i’ = 0 to ‘N - 1’.
- Define ‘BALANCECHANGE’ as the difference between ‘AVERAGEBALANCE’ and ‘ARR[i]’.
- If ‘BALANCECHANGE’ is not divisible by ‘K’, then we will return -1. As it is impossible to make the wallet balance of all friends equal.
- If ‘BALANCECHANGE’ is positive, then we will add the quotient of the division of ‘BALANCECHANGE’ by ‘K’ to ‘TRANSACTIONCOUNT’. We are not adding transactions for negative ‘BALANCECHANGE’, because, in one transaction, the balance of one friend decreases by ‘K’, and the balance of some other friend decreases by ‘K’ simultaneously. So we can consider all the positive ‘BALANCECHANGE’, or we can consider only the negative ‘BALANCECHANGE’.
- Return the ‘TRANSACTIONCOUNT’ variable.
