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


  • Approach:

    1. Firstly, calculate the average of the given numbers, AVG. ( i.e. Total sum of numbers given in arr/size of arr ).

    2. Also, check if every number in arr is equal or not. If equal then returned 0.

    3. Initiated maxNeg = 0, maxPos = 0, req = 0

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

    5. Now, if the req is zero, returned -1.

    6. 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);

}