How to divide an integer array into 2 sub-arrays and make their averages equal?

Question

Please help me with the above question. An algorithm with a working example will be appreciated. Also, please handle the case where the above is not possible.

It’s good that I still have the following:

Go through the whole array and get the average value of the whole array. On the). Call it avg

Then, from this average, the average value of the entire array can be obtained, except for a[0] (formula: avg(a[1..n-1])=(avg(a[0..n-1])*na[0])/(n-1) ). Then you take this new average and compare it with [0]. If they are not equal, you move on to the next value, which calculates the averages from previously known averages, using the formula above.

Although someone has provided me with a solution that "works", I am looking for the most efficient implementation.

Answer 1

A quick google search returned this . In any case, if you are not looking for performance, backtracking is always an option.

EDIT: I tried applying rollback. My solution is in no way ineffective. You can, of course, replace medium-sized methods to avoid a different level of cycling. In addition, to show that there is no solution, you can simply count the number of solutions.

 import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; import java.util.List; public class SOQuestion { /** * just prints a solution * * @param list * @param indexes */ public static void printSolution(List list, HashSet indexes) { Iterator iter = indexes.iterator(); while (iter.hasNext()) { System.out.print(list.get((Integer) iter.next()) + " "); } System.out.println(); } /** * calculates the average of a list, but only taking into account the values * of at the given indexes * * @param list * @param indexes * @return */ public static float avg(List list, HashSet indexes) { Iterator iter = indexes.iterator(); float sum = 0; while (iter.hasNext()) { sum += (Integer) list.get((Integer) iter.next()); } return sum / indexes.size(); } /** * calculates the average of a list, ignoring the values of at the given * indexes * * @param list * @param indexes * @return */ public static float avg_e(List list, HashSet indexes) { float sum = 0; for (int i = 0; i < list.size(); i++) { if (!indexes.contains(i)) { sum += (Integer) list.get(i); } } return sum / (list.size() - indexes.size()); } public static void backtrack(List list, int start, HashSet indexes) { for (int i = start; i < list.size(); i++) { indexes.add(i); if (avg(list, indexes) == avg_e(list, indexes)) { System.out.println("Solution found!"); printSolution(list, indexes); } backtrack(list, i + 1, indexes); indexes.remove(i); } } public static void main(String[] args) { List test = new ArrayList(); test.add(2); test.add(1); test.add(3); backtrack(test, 0, new HashSet()); } } 

Answer 2

Here is how I did it:
1 - General array → if an odd number cannot create two separate arrays. O (n)
2 - Divide the total by 2.
3 - Array Sort (from highest to lowest) → O (NLogN)
4 - Start with the highest number and continue to try to get the remaining amount by moving to the next highest number. If you cannot do this, move the number to another array. → I think the worst case is O (N ^ 2).

So let's look at this example: 3, 19, 7, 4, 6, 40, 25, 8

• Total = 112
  
• Divide by 2 = 56
  
• Array sorting - 3, 4, 6, 7, 8, 19, 25, 40
  
• → 40 in list 1 (list 1 total = 40, 16 remaining)
  -> 25 is too large, in list 2 (list 2 total = 25)
  -> 19 is too large, in list 2 (list 2 total = 44)
  -> testing 8 in list 1 (list 1 total = 48, 8 remaining)
  -> Testing 7 in list 1 (list 1 total = 55, 1 left)
  -> there is no way to add another 1 | -> 7 failed test 6 (list 1 total = 54, 2 left)
  -> there is no way to add another 2 -> 6 failure test 4 (total 2 lists - 52, 4 remaining)
  -> no way to add 2 more -> 4 crash test 3
  -> 3 does not return 8 -> Move 8 to list 2 and start testing 7 (list 1 total = 47, 9 remaining, list 2 total = 52)
  -> Testing 6 (list 1 total = 53, 3 remaining)
  -> Add 3 items (list 1 total = 56, success)
  

Thus, two lists: [40,7,6,3] and [25,19,8,4]

Answer 3

Try this code ...

 #include <QList> #include <QDebug> /**** We sort the array in the desending order. So the first two elemnts are the biggest element of the array. These are put in split1 and the split2 array. Note that we start from the biggest element the average is going to be much higher than the final avarage. Next we start placing the smaller elemnts from source to split1 or split2. To do this we make a simple dicision. We look at the value to be added and then see if that will increase/decrease the average of a given split. Accordingly we make our decesion. ****/ static bool averageSplit(const QList<int>& source, QList<int>& split1, QList<int>& split2) { if (source.size() < 2) { return false; } QList<int> list = source; qSort(list.begin(), list.end(), qGreater<int>()); double sum = 0; foreach(int elm, list) { sum += elm; } const double totalAvg = sum / list.size(); double sum1 = list[0]; double sum2 = list[1]; split1.append(list[0]); split2.append(list[1]); for(int i = list.size() - 1; i >= 2; --i) { double avg1 = sum1 / split1.size(); double avg2 = sum2 / split2.size(); int val = list[i]; if (avg1 < avg2) { // Try to increase tha avg1 or decrease avg2. if (val > split1.size()) { split1.append(val); sum1 += val; } else { split2.append(val); sum2 += val; } } else { // Try to increase tha avg2 or decrease avg1. if (val > split2.size()) { split2.append(val); sum2 += val; } else { split1.append(val); sum1 += val; } } } qDebug() << "totalAvg " << totalAvg; qDebug() << "Avg1 " << sum1 / split1.size(); qDebug() << "Avg2 " << sum2 / split2.size(); } void testAverageSplit() { QList<int> list; list << 100 << 20 << 13 << 12 << 12 << 10 << 9 << 8 << 6 << 3 << 2 << 0; list << -1 << -1 << -4 << -100; QList<int> split1; QList<int> split2; averageSplit(list, split1, split2); qDebug() << "split1" << split1; qDebug() << "split2" << split2; } 

Answer 4

I think that if the SUM of all elements in the original array is odd, then dividing into 2 arrays is not possible. however, if sum == even, you can start creating your array so that the sum of the elements in each == SUM / 2

Answer 5

 #include<stdio.h> void partitionEqualAvt(int *a, int n) { int i; int sum=0, sSum=0, eSum, sAvg, eAvg; for(i=0; i<n; i++) sum+=a[i]; eSum=sum; for(i=0; i<n-1; i++) { sAvg=0; eAvg=0; sSum+=a[i]; eSum=sum-sSum; sAvg=sSum/(i+1); eAvg=eSum/(ni-1); if(sAvg == eAvg) { printf("\nAverage = %d from [%d to %d] and [%d to %d]", sAvg, 0, i, i+1, n); } } } int main() { int a[]={1,1,1,1,1,1}; int n=sizeof(a)/sizeof(int); partitionEqualAvt(a,n); return 0; } 

Answer 6

Using the Greedy Algorithm One approach to the problem that mimics how children select teams to play with is a greedy algorithm that iterates over numbers in descending order, assigning each of them a smaller subset. This works well when the numbers in a set are about the same size as its power or less.

Try this in python: If an average exists, then this one can find it, otherwise it will bring you closer to an equal average.

  a = [500, 1, -45, 46, -20, 100, -30, 4, 110] b, c = [], [] m1, m2, n1, n2 = 0, 0, 0, 0 count = 0 for i in a: if count == 0: b.append(i) n1 += 1 m1 = i n1 = 1 count = 1 continue else: tmp_m1 = (m1 * n1 + i) / (n1 + 1) tmp_m2 = (m2 * n2 + i) / (n2 + 1) print b, c, tmp_m1, tmp_m2 if m1 > m2: if(tmp_m1 - m2 < m1 - tmp_m2): b.append(i) m1 = tmp_m1 n1 += 1 else: c.append(i) m2 = tmp_m2 n2 += 1 else: if(tmp_m1 - m2 < m1 - tmp_m2): c.append(i) m2 = tmp_m2 n2 += 1 else: c.append(i) m1 = tmp_m1 n1 += 1 print b, c, m1, m2 Sample output: [500] [] 250 1 [500, 1] [] 151 -45 [500, 1, -45] [] 124 46 [500, 1, -45] [46] 108 13 [500, 1, -45, -20] [46] 106 73 [500, 1, -45, -20] [46, 100] 80 38 [500, 1, -45, -20, -30] [46, 100] 67 50 [500, 1, -45, -20, -30, 4] [46, 100] 73 85 [500, 1, -45, -20, -30, 4] [46, 100, 110] 73 73