Suppose u have an array {1,2,4,5} U divide it into {1,5} and {2,4}. U get the average same.
If the array {1,2,3,6,5} is subdivided into {2,3,5} and {1,6} the average would be 3.33 and 3.5. In this case, the average can't be equal.

What exactly is expected in this case?

First go through the array and sum up the integers then divide it by two.
let half = sum(array)/2;
Now find a subset of integers in the array such that the sum is equal to half. There are cases where no solution exist.
As you can see, finding subset then sum up the subset has many redundancies. Using dynamic programming can make this problem faster.
There is a ACM UVA problem called Tug of War that is similar to this.

The key is the phrase divide the array into two subarrays. therefore you can only have average(array[0..i])=average(array[i+1..n-1]) assuming fo course that this is made possible by the values in the array. Doing the brute force will be something like take the array[0..i] and array[i+1..n-1], make the average for the two subarrays and compare them for each i from 0 to n-1. This in unnecesary. You can do first the average of the whole array. Then from this average can get the average of the whole array excetp a[0] (the formula is: avg(a[1..n-1])=(avg(a[0..n-1])*n-a[0])/(n-1)). 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.

First compute the average of the entire array (lets call it 'avg')

Now start from a[0], see if a[0] == avg... then take avg of a[0] to a[1], see if its equal to avg.. and so on...

this will work, coz if 2 parts of a set have the same average, then the average of both parts is also the same!

#define N  5
main()
{
int arr[N] = {15,12,9,1,23};
int i;
int sum = 0;
float avg;


/* Calculate avg of entire arr */
for (i = 0; i < N; i++)
    sum += arr[i];

avg = (float)sum / N;
sum = 0;

/* Compute moving average. (N - 1) is *not* a typo - we want to stop before putting in the last element */
for (i = 0; i < N - 1; i++) {
    sum += arr[i];
    if (avg == (float)sum / (i+1)) {
         printf("Divide @ %d\n", i);
         return;
    }
}

printf("Arr is not suitable\n");
return;
}

Use cross-multiplication if you want to avoid the pesky floats...

Here is my algo for this thingy:

1. Find the average of the array
2. Sort the array in ascending order
3. Pick the last element in the array (the biggest) and put it in subarray1
4. Keep on picking the elements from the beginning of the array untill the average of subarray1 becomes equal to the average of the original array. The elements remaining in the original array form the 2nd array.

[Note that there is no constraint in the original question to balance the arrays].

Raja you algo wont work for this input
3 5 9 11 15 20

1. calculate the average of the array (called it ave)
2.sort the array
3. keep two pointer,one from the begining of the sorted array, the other endof the sorted array. starting from calculating of the first and last element. if the average=ave, print the subarray which is composed of the elements whose index are stored in the two pointers. if the average<ave, add the element which the first pointer is pointing and move the pointer forward, if the average>ave, add the element which the second pointeris pointing andmove the pointer backward; and calculate the average, continue this till average=ave.
void getsubArray(int a[],int n,int ave)
{
int i=0;
int j=n-1;
sum=a[i]+a[j];
count=2;
int average=sum/count;
while(i<=j)
{
if(average==ave)
{for(int s=0;s<=i;s++)
printf("%d",a[s]);
for(int s=n-1;s>=j;s++)
printf("%d",a[s]);
}
if(average<ave)
{
sum+=a[++i];
}
else
sum+=a[++j];

average=sum/(++count);


}

}

its a NP problem
subset sum problem

subset sum, using dynamic programming to solve

given: array A[1...n]

// first calculate the sum
int sum = A[1] + A[2] + ... A[n];

// if sum is odd, no such equal partition exists
if( sum % 2 != 0) return false;

// a boolean array initialized to all false except the first element
int workable[sum];
memset(workable, 0, sizeof(workable);
workable[0] = 1;
for(int i = 1; i <= n; ++i)
for(int s = sum; s >= 0; --s)
if(workable[s])
workable[s + A[i]] = 1;

return workable[sum/2];

I don't get the problem well let say we have 100,0,1 how one can divide it into two such subarray?

You can't divide in that case, you poor man!

int intarray[10];
int Sum;

/*find sum*/

for ( i = 0; i< 10; i++)
{sum += intarray[i]}

/*find average*/

int Avg;

Avg = sum / 10;

sum = 0;

/*find half array*/

for( i = 0; i<10
; i++)

{
while ((sum+= intarray[i] )/(i+1) !== avg);
}

print f ( " Array has been broken down, first %d elements in first array and remaining ones in the other, i+1)

int intarray[10];
int Sum;

/*find sum*/

for ( i = 0; i< 10; i++)
{sum += intarray[i]}

/*find average*/

int Avg;

Avg = sum / 10;

sum = 0;

/*find half array*/

for( i = 0; i<10
; i++)

{
while ((sum+= intarray[i] )/(i+1) !== avg);
}

print f ( " Array has been broken down, first %d elements in first array and remaining ones in the other, i+1)

int intarray[10];
int Sum;

/*find sum*/

for ( i = 0; i< 10; i++)
{sum += intarray[i]}

/*find average*/

int Avg;

Avg = sum / 10;

sum = 0;

/*find half array*/

for( i = 0; i<10
; i++)

{
while ((sum+= intarray[i] )/(i+1) !== avg);
}

print f ( " Array has been broken down, first %d elements in first array and remaining ones in the other, i+1)

This is a famous balanced partitioning . Its best approach is to use Dynamic Programming. Find it on Google.

Balanced partitioning is just about dividing into two subsets with equal sums(?). This has more constraint.

"Rohith Menon on August 18"'s solution is pretty close.

Hi, This is a very straight forward dynamic programming problem. But works if the sum of the numbers is small. We have to find if the average of the array is same as average of some subset.Say the average of the array is stored in say a Variable reqAvg. The psuedo code is as follows.

bool isAveragePossible(int n=0,int sum=0,int index=0){
                if(index==arraysize)
                               return (n>0)?(sum/(double)n==reqAvg):0;
                if(dp[index][n][sum]!=-1)
                             return dp[index][n][sum];
                else
                    return dp[index][n][sum]=isAveragePossible(n+1,sum+arr[index],index+1)||isAveragePossible(n,sum,index+1);


}

Hi, This is a very straight forward dynamic programming problem. But works if the sum of the numbers is small. We have to find if the average of the array is same as average of some subset.Say the average of the array is stored in say a Variable reqAvg. The psuedo code is as follows.

bool isAveragePossible(int n=0,int sum=0,int index=0){
if(index==arraysize)
return (n>0)?(sum/(double)n==reqAvg):0;
if(dp[index][n][sum]!=-1)
return dp[index][n][sum];
else
return dp[index][n][sum]=isAveragePossible(n+1,sum+arr[index],index+1)||isAveragePossible(n,sum,index+1);

}