hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Distribution of Money
Problem: Distribution of Money
Problem Link: https://www.codingninjas.com/codestudio/problems/distribute-money-between-friends_1229503
Approach:
Firstly, calculate the average of the given numbers, AVG. ( i.e. Total sum of numbers given in arr/size of arr ).
Also, check if every number in arr is equal or not. If equal then returned 0.
Initiated maxNeg = 0, maxPos = 0, req = 0
For each ith number in arr -
Assign, rem = arr[i] - AVG.
If ABS(rem) % K is not zero, then returned -1.
If rem < 0, then added (abs(rem) / K) with maxNeg.
Else added (rem / K) with maxPos.
Added rem with req.
Now, if the req is zero, returned -1.
Then return max(maxNeg, maxPos).
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(1)
Code [C++]
#include <bits/stdc++.h>
int minTransactions(int k, vector < int > & arr) {
int n = arr.size(), sum = arr[0];
bool equal = true;
for(int i=1; i<n; i++){
if(arr[i] != arr[i-1]) equal = false;
sum += arr[i];
}
if(equal) return 0;
int average = sum / n;
int req = 0, maxNeg = 0, maxPos = 0;
for(int i=0; i<n; i++){
int rem = arr[i] - average;
if(abs(rem) % k) return -1;
if(!rem) continue;
if(rem < 0) maxNeg += (abs(rem) / k);
else if (rem > 0) maxPos += (abs(rem) / k);
req += rem;
}
if(req) return -1;
return max(maxNeg, maxPos);
}