title: how to divide an integer array into 2 sub-arrays and make their averages equal?
body: <p>Please help me with the above question. An algorithm with a working example will be appreciated. Also, please handle the case when the above is not possible.</p>
  
  <p>Okay, what I have till now is the following:</p>
  
  <p>Go through entire array and get average of whole array. O(n). Let us call this avg</p>
  
  <p>Then from this average can get the average of the whole array except <code>a[0]</code> (the formula is: <code>avg(a[1..n-1])=(avg(a[0..n-1])*n-a[0])/(n-1)</code>). Then you take this new average and compare it with a[0]. If they are not equal you move to the next value calculating the averages from the previously know averages using the formula from above.</p>
  
  <p>Though someone has provided me a solution that "works", I am looking for the most efficient implementation.</p>