CareerCup

Assume that such splitting exists.
Let then N be array length, Sum - sum of entire array, P - sum of one part of items, K - count of numbers in that part.
Let's write equations for averages in both parts of array:

P / K = (Sum - P) / (N - K)
P * (N - K) = K * (Sum - P)
P * N - P * K = K * Sum - K * P
P * N = K * Sum
P = K * Sum / N

Now we can easily check if such P can be integer (we operate with array of integers).
If so, we reduce our problem to picking K integers with sum of P from sorted array of integers.
C# code:

static List<int> GetSum(int[] numbers, int count, int needSum)
{
    // numbers must be sorted
    List<int> result = new List<int>();

    // can apply memoization to rec
    Func<int, int, int, bool> rec = null;
    rec = (index, cnt, sum) =>
    {
        if (sum == 0) return cnt == 0;
        if (index == numbers.Length) return false;

        for (int j = index; j < numbers.Length; j++)
        {
            result.Add(j);
            if (rec(j + 1, cnt - 1, sum - numbers[j])) return true;
            result.Remove(j);
        }

        return false;
    };
    return rec(0, count, needSum) ? result : null;
}

// returns indices of left part or null, if array cannot be splitted
static List<int> Divide(int[] numbers)
{
    Array.Sort(numbers);
    int sum = numbers.Sum();
    int n = numbers.Length;
    for (int k = 1; k <= n - k; k++)
    {
        if (k * sum % n != 0) continue;
        int p = k * sum / n;
        List<int> tmpRes = GetSum(numbers, k, p);
        if (tmpRes != null) return tmpRes;
    }
    return null;
}

static void Main(string[] args)
{
    int[] arr = new int[] { 1, 7, 15, 29, 11, 9 };
    List<int> leftIndices = Divide(arr);
    if (leftIndices == null)
        Console.WriteLine("No solution");
    else
    {
        Console.WriteLine("Whole array:");
        Console.WriteLine(string.Join(" ", arr));
        Console.WriteLine("Left part:");
        Console.WriteLine(string.Join(" ", leftIndices.Select(i=>arr[i])));
    }
}

If we look at the averages in another way, the problem is asking whether it is possible to divide the set into two subsets such that the sum of elements of one subset is a multiple of sum of elements of another subset. Apparently, this is a variant of partition problem and I think some existing DP algorithms should work, though I haven't worked out the details.

If we look at the averages in another way, the problem is asking whether it is possible to divide the set into two subsets such that the sum of elements of one subset is a multiple of sum of elements of another subset. Apparently, this is a variant of partition problem and I think some existing DP algorithms should work, though I haven't worked out the details.

How do you know it was bar raiser?

How do you know it was bar raiser?

How do you know it was bar raiser?

How do you know it was bar raiser?

How do you know it was bar raiser?

How do you know it was bar raiser?

Sorting is not a solution

//(Bar Raiser Round)
//Divide the array(+ve and -ve numbers) into two parts such that the
//average of both the parts is equal.

//[1 7 15 29 11 9] 
// Part1:- 15,9    Avg = 12
//Part2:- 1,7,11,29 Avg = 48/4=12


void DivideArray(int arr[],int i,int n,int sum,int part1[],int index1,int part2[],int index2)
{
   if(i > n)
   {
      return;
   }
   
   if(i == n)
   {
       if(index1 == 0 || index2 == 0) return;

       int s = 0;

       for(int p = 0; p < index1; p++)
       {
          s+=part1[p];
       }

       if(s/index1 == (sum -s)/(n-index1))
       {
          cout<<"\nPart1:-";
          for(int c = 0; c < index1; c++)
          {
             cout<<part1[c]<<"  ";
          }
          cout<<"\nPart2:-";
          for(int c = 0; c < index2; c++)
          {
             cout<<part2[c]<<"  ";
          }
       }
       return;
   }
   else
   {
      part1[index1] = arr[i];
      DivideArray(arr,i+1,n,sum,part1,index1+1,part2,index2);
      part2[index2] = arr[i];
      DivideArray(arr,i+1,n,sum,part1,index1,part2,index2+1);
   }
}
int main()
{

   int arr[] = {1,7,15,29,11,9};

   int n = sizeof(arr)/sizeof(arr[0]);

   int sum = 0;

   for(int i = 0; i < n; i++)
   {
       sum +=arr[i];
   }
 
   int *part1 = new int[n];
   int *part2 = new int[n];
   DivideArray(arr,0,n,sum,part1,0,part2,0);
   return 0;
}

Output:-
Part1:-1 7 29 11
Part2:-15 9
Part1:-15 9
Part2:-1 7 29 11

This will work, if the array will divide into two parts.
Time Complexity: O (n)
Is it correct or not?
Please reply me
Thanks in advance.

package com.cnu.ds;

import java.util.LinkedList;
import java.util.Queue;

public class DivideArray {
	public static void name(int[] a) {
		int sum1, sum2;
		sum1 = a[0];
		sum2 = 0;
		Queue<Integer> queue1 = new LinkedList<>();
		Queue<Integer> queue2 = new LinkedList<>();
		boolean b = false;
		for (int i = 1; i < a.length; i++) {
			if (sum1 >= sum2 && a[i] > 0) {
				queue2.add(a[i]);
				sum2 += a[i];
			} else {
				queue1.add(a[i]);
				sum1 += a[i];
			}
		}
		int i = 0;
		while (sum1 != sum2) {
			if (sum1 > sum2) {
				i = queue1.remove();
				queue2.add(i);
				sum2 += i;
				sum1 -= i;
			} else if (sum1 < sum2) {
				i = queue2.remove();
				queue1.add(i);
				sum1 += i;
				sum2 -= i;
			}
		}
		i = 0;
		while (!queue1.isEmpty()) {
			a[i++] = queue1.remove();
		}
		while (!queue2.isEmpty()) {
			a[++i] = queue2.remove();
		}
		for (Integer integer : a) {
			System.out.print(integer + " ");
		}
	}
}

i can think of a o(n^3) solution. for any sequence we can divide the array into contiguous subsequences 0 to i and i to n. we can easily check whether avg of these two subsequences is equal. iterating and check avg takes o(n) for a particular sequence.

Number of such sequences=o(n^2).

Total time complexity is: o(n^3)

Just one observation I had is: in the given solution the min value is in the middle and then other values are added to the each side of the min value in increasing order. So, I was wondering whether if we can have a solution just by sorting the array and then take the first element and add the other values in the series to each side of it like this:
1, 7 --> 9, 1, 7 --> 9, 1, 7, 11 --> 15, 9, 1, 7, 11 --> 15, 9, 1, 7, 11, 29

bool divide(int arr[], int curr, int n, int s1, int s2, int res[], int n1, int n2)
{
if ((n == curr) && ((float) s1/n1 == (float) s2/n2))
return true;
else if (n == curr)
return false;
else
{
res[curr]= -1;
if (divide(arr, curr + 1, n, s1 + arr[curr], s2, res, n1 + 1, n2))
return true;

res[curr]= 1;
if (divide(arr, curr + 1, n, s1, s2 + arr[curr], res, n1, n2 + 1))
return true;
}

return false;
}

1. Get sum all elements
2. Until the right combination will not be found, iterate over all combinations, which start from 1st element (because 1st element always will be in left combination) and stop when count of elements less than array length - 1 (because result array must have two parts)
3. If such combination found, rearrange the elements in array

O(2^(n-1) - 1)

public static int DivideArray(int[] arr)
{
    const int DivisionNotFound = -1;

    // Checks
    if (arr == null || arr.Length == 0)
        return DivisionNotFound;

    if (arr.Length == 1)
        return DivisionNotFound;

    if (arr.Length == 2)
    {
        if (arr[0] != arr[1])
            return DivisionNotFound;
        return 0;
    }

    // Get sum
    var sum = 0;
    for (var i = 0; i < arr.Length; i++)
    {
        sum += arr[i];
    }

    // Search combinations
    var combination = new bool[arr.Length];
    combination[0] = true;

    if (!FindSubSet(arr, combination, 1, sum, arr[0], 1))
        return DivisionNotFound;

    // Rearrange
    var lp = 0;
    var rp = combination.Length - 1;
    while (lp <= rp)
    {
        while (combination[lp])
            lp++;
        while (!combination[rp])
            rp--;
        if (lp < rp)
        {
            var tmp = arr[lp];
            arr[lp] = arr[rp];
            arr[rp] = tmp;
            combination[lp] = true;
            combination[rp] = false;
            lp++;
            rp--;
        }
    }

    return lp - 1;
}

private static bool FindSubSet(int[] arr, bool[] combination, int pos, int sum, int incSum, int incCount)
{
    incCount++;

    if (incCount > arr.Length - 1)
        return false;

    for (var i = pos; i < arr.Length; i++)
    {
        incSum += arr[i];
        combination[i] = true;

        if (incSum%incCount == 0 && (sum - incSum)%(arr.Length - incCount) == 0)
        {
            // average must be integer
            if (incSum/incCount == (sum - incSum)/(arr.Length - incCount))
                return true;
        }

        if (FindSubSet(arr, combination, i + 1, sum, incSum, incCount))
            return true;

        combination[i] = false;
        incSum -= arr[i];
    }

    return false;
}

Here is solution on D:

This can be tested on dpaste.dzfl.pl/61c4d824195f
import std.stdio;
import std.conv;
import std.typecons;
import std.algorithm;
import std.exception;
import std.c.math;
/*
(Bar Raiser Round)
Divide the array(+ve and -ve numbers) into two parts such that the average of both the parts is equal.

Input:
[1 7 15 29 11 9]

Output:
[15 9]  [1 7 11 29]

Explanation:
The average of first two elements is (15+9)/2 = 12, average of remaining elements is (1 + 7 + 11 + 29)/4 = 12
*/

int calculateP(int S, size_t N, size_t K)
{	
	if (N <= 0 || K <= 0 || K >= N)	return 0;
	double intPart;
	double doubleP = K * S / to!double(N);
	bool isInt = (0.0 == modf(doubleP, &intPart));
	return (S > doubleP && isInt) ? (to!int(doubleP)) : 0;
}

unittest
{
	assert(calculateP(0,1,1) == 0); 
	assert(calculateP(1,0,1) == 0); 
	assert(calculateP(1,1,0) == 0); 
	assert(calculateP(10, 5, 2) == 4); /// 10 * 2 / 5 
}

int[] findSubarray(int[]a, int P, size_t K) 
{	
	/// This should return the subarray of the K items with total sum of P	
	if (K <= 0) throw new Exception("The 'K' should be positive.");
	if (K >= a.length) throw new Exception("The 'K' should be less than 'a.length'.");
	if (!isSorted(a))
	{
		int[] a_copy = a.dup;
		sort(a_copy);
		return findSubarray(a_copy, P, K);
	}

	switch(K)
	{
		case 1: 
			return findSplit(a, [P])[1];
		case 2:
			while (a.length > 1)
			{
				int S = a[0] + a[$-1];
				if (P == S) return [a[0], a[$-1]];
				a = (S > P) ? a[0..$-1] : a[1..$];
			}
			return [];
		default:
			foreach(i, item; a)
			{		
				int[] res = findSubarray(a[0..i] ~ a[i+1..$], P - item, K - 1);
				if (res.length) return [item] ~ res;
			}
	}
	return [];
}

int SumOfArray(int[] a)
{
	return reduce!"a+b"(0, a);
}

double AvgOfArray(int[] a)
{
	return SumOfArray(a) / to!double(a.length);
}

unittest
{
	int[] a = [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6];
	int[] Sub;
	for (size_t K = 1; K < a.length; K += 2)
	{
		for(int P = -5; P <= 5; ++P)
		{
			Sub = findSubarray(a,P,K);
			assert((P == SumOfArray(Sub) && Sub.length == K) || Sub.length == 0);
		}
	}
}

Tuple!(int[], int[]) divideByTemplate(int[]a, int[] templ)
{
	Tuple!(int[], int[]) result;
	foreach(elem; a)
	{
		if (templ.length == 0) break;
		auto parts = findSplit(templ, [elem]);
		if (parts[1].length > 0)
		{
			result[0] ~= parts[1];
			templ = parts[0] ~ parts[2];
		}
		else
		{
			result[1] ~= elem;
		}		
	}
	return result;
}

unittest
{
	int[] a = [1, 7, 15, 29, 11, 9];
	int[] templ = [9, 15];
	auto tuple = divideByTemplate(a, templ);
	assert(tuple[0] == [15,9] && tuple[1] == [1, 7, 29, 11]);
}

Tuple!(int[], int[]) doSplit(int[] a)
{	
	size_t N = a.length;
	int S = SumOfArray(a);
	for(size_t K = 0; K <= N; ++K)
	{
		int P = calculateP(S, N, K);
		int[] Sub = (P > 0) ? findSubarray(a,P,K) : [];
		if (P == SumOfArray(Sub) && Sub.length == K && K > 0)
		{
			return divideByTemplate(a, Sub);			
		}
	}
	return tuple!(int[], int[])([],[]);
}


void doDemo(int[] a)
{
	auto tuple = doSplit(a);
	if (tuple[0] && tuple[1])
	{
		writeln("One of the possible division for this array ", a, " is " , tuple[0], " and ", tuple[1], ". Avg for this ", AvgOfArray(tuple[0]), " and ", AvgOfArray(tuple[1]) );
	}
	else
	{
		writeln("This array ", a, " could not be divided");
	}

}

unittest
{
	doDemo([1, 7, 15, 29, 11, 9]);
	doDemo([1, 3, 5, 7, 13, 17]);
	doDemo([1, -3, 2, -1, -1, 6]);
}


int main(string[] argv)
{
    return 0;
}

Application output

One of the possible division for this array [1, 7, 15, 29, 11, 9] is [15, 9] and [1, 7, 29, 11]. Avg for this 12 and 12
One of the possible division for this array [1, 3, 5, 7, 13, 17] is [1, 5, 17] and [3, 7, 13]. Avg for this 7.66667 and 7.66667
One of the possible division for this array [1, -3, 2, -1, -1, 6] is [-3, -1, 6] and [1, 2, -1]. Avg for this 0.666667 and 0.666667

My recursive solition. It rearranges array in place and return the length of the left part (or -1 if no solution exists).

int divide_impl(int *a, int llen, int rlen, int lsum, int sum) {
  if (rlen == 0) return -1;
  if (llen > 0 && lsum * rlen == (sum - lsum) * llen) {
    return llen;
  }
  for (int i = 0; i < rlen; i++) {
    swap(a[0], a[i]);
    int r = divide_impl(a + 1, llen + 1, rlen - 1, lsum + a[0], sum);
    if (r >= 0) return r;
    swap(a[0], a[i]);
  }
  return -1;
}

int divide(int *a, int n) {
  int sum = accumulate(a, a + n, 0);
  return divide_impl(a, 0, n, 0, sum);
}

Java solution based on Flux's code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class AvgArray {
	private static List<Integer> result = new ArrayList<Integer>();
	private static List<Integer> original = new ArrayList<Integer>();
	
	private static boolean checkSum(int index, int count, int sum) {
		if(count == 0) return sum == 0;
		if(sum == 0) return count == 0;
		if(index == original.size()) return false;
		
		for(int j=index;j<original.size();j++) {
			System.out.println("add index: "+j+"; number: "+original.get(j));
			result.add(j);
			//System.out.println("result array: "+result.toString());
			if(checkSum(j+1, count-1, sum-original.get(j))) return true;
			System.out.println("remove index: "+j+"; number: "+original.get(j));
			result.remove((Integer)j);
			//System.out.println("result array: "+result.toString());
		}
		
		return false;
	}
	
	private static List<Integer> getSum(int count, int sum) {
		System.out.println("count: "+count+"; sum: "+sum);
		return checkSum(0, count, sum) ? result : null;
	}
	
	private static List<Integer> divide(List<Integer> numbers) {
		Collections.sort(numbers);
		System.out.println("Sorted: "+numbers.toString());
		int sum = 0;
		int size = numbers.size();
		for(int i=0;i<size;i++) {
			sum += numbers.get(i);
		}
		for(int k=1;k<size-k;k++) {
			if(k*sum%size != 0) continue;
			int p= k*sum/size;
			//System.out.println("p: "+p+"; k: "+k);
			List<Integer> tempRes = getSum(k, p);
			if(tempRes != null) return tempRes;
		}
		return null;
	}
	
	public static void main(String[] args) {
		original.add(1);
		original.add(7);
		original.add(15);
		original.add(29);
		original.add(11);
		original.add(9);
		
		List<Integer> left = divide(original);
		if (left == null)
			System.out.println("No solution");
		else {
			StringBuilder sb = new StringBuilder();
			sb.append(original.get(left.get(0)));
			for(int i=1;i<left.size();i++) {
				sb.append(", " + original.get(left.get(i)));
			}
			System.out.println(sb.toString());
		}
	}

}

test output:

Sorted: [1, 7, 9, 11, 15, 29]
count: 1; sum: 12
add index: 0; number: 1
remove index: 0; number: 1
add index: 1; number: 7
remove index: 1; number: 7
add index: 2; number: 9
remove index: 2; number: 9
add index: 3; number: 11
remove index: 3; number: 11
add index: 4; number: 15
remove index: 4; number: 15
add index: 5; number: 29
remove index: 5; number: 29
count: 2; sum: 24
add index: 0; number: 1
add index: 1; number: 7
remove index: 1; number: 7
add index: 2; number: 9
remove index: 2; number: 9
add index: 3; number: 11
remove index: 3; number: 11
add index: 4; number: 15
remove index: 4; number: 15
add index: 5; number: 29
remove index: 5; number: 29
remove index: 0; number: 1
add index: 1; number: 7
add index: 2; number: 9
remove index: 2; number: 9
add index: 3; number: 11
remove index: 3; number: 11
add index: 4; number: 15
remove index: 4; number: 15
add index: 5; number: 29
remove index: 5; number: 29
remove index: 1; number: 7
add index: 2; number: 9
add index: 3; number: 11
remove index: 3; number: 11
add index: 4; number: 15
9, 15

assuming such splitting exists, get the average of the whole array, The average of the 2 parts should also be equal to this average. Then we need to find a subset of the array that averages to this. This can be got by the subset solution :(O2^n)

int max = 1 << set.size();
vector <int> subset1,subset2;
for (i=1;i<max,i++) {
   int k=i;
   int index = 0,cnt=0,sum=0;
   subset1.empty();
   while (k>0) {
      if((k&1)>0) {
          cnt++;
          subset1.insert(index);
          sum+=arr[index];
      }
      index++;
      k>>1;
      }
        if (sum/cnt==AVG) {
           break;
        }
}

//Now get subset2:

   set<int>::iterator it = subset.begin();
   for(i=0;i<set.size();i++) {
     if (i!=*it) {
        subset2.insert(i);
      } else 
        ++*it;
   }

}

this might help
I found it on wikipedia with name :Partition_problem
The code is copied from there

//pseudo-polynomial algorithm
public static bool balancePartition(int[] S)
{
var n = S.Length;
var N = S.Sum();
bool[,] P = new bool[N / 2 + 1, n + 1];
for (int i = 0; i < n + 1; i++)
P[0, i] = true;
for (int i = 1; i < N / 2 + 1; i++)
P[i, 0] = false;
for (int i = 1; i <= N / 2; i++)
for (int j = 1; j <= n; j++)
P[i, j] = S[j - 1] <= i ? P[i, j - 1] || P[i - S[j - 1], j - 1] : P[i, j - 1];
return P[N / 2, n];
}

{{#include<iostream>
#include<vector>
using namespace std;


bool isSumMatch(int A[], vector<int> v, int i, int l, int n, int P, int sum)
{
if(l==0){
if(sum == P)
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
}
else{
for(int t=i;t<n;t++){
v.push_back(A[t]);
isSumMatch(A, v, t+1, l-1,n, P, sum+A[t]);
v.pop_back();
}
}

}
int main(){

int A[]={1, 7, 15, 29, 11, 9};
int sum = 0;
int n = 6;
for(int i=0;i<n;i++){
sum+=A[i];
}

int avg=sum/n;
vector<int> v;
for(int l=1;l<n/2;l++){
v.clear();
if(isSumMatch(A, v, 0, l, n, avg*l, 0))
break;
}

}}}

The problem can be solved in linear time:

1) get the average. ( linear time)
2) substract the average from each number in the array
3) partition on +ve and -ve numbers. As we know that the total sum of both will certainly be 0.
4) works for integer +ve or -ve numbers.

The problem can be solved in linear time:

1) get the average. ( linear time)
2) substract the average from each number in the array
3) partition on +ve and -ve numbers. As we know that the total sum of both will certainly be 0.
4) works for integer +ve or -ve numbers.

Its recursive, basically do a bool Split(remainingArray, leftArray, RightArray, leftAverage, rightAverage).
At each round pull the next element and then call Split two times, once for adding it to left with updatedAverage etc. and once for Adding it to right. Whichever returns true return that value.
You can trace this against a simple 1, 2, 1.5 before you right the algorithm.

Its recursive, basically do a bool Split(remainingArray, leftArray, RightArray, leftAverage, rightAverage).
At each round pull the next element and then call Split two times, once for adding it to left with updatedAverage etc. and once for Adding it to right. Whichever returns true return that value.
You can trace this against a simple 1, 2, 1.5 before you right the algorithm.

Its recursive, basically do a bool Split(remainingArray, leftArray, RightArray, leftAverage, rightAverage).
At each round pull the next element and then call Split two times, once for adding it to left with updatedAverage etc. and once for Adding it to right. Whichever returns true return that value.
You can trace this against a simple 1, 2, 1.5 before you right the algorithm.

Rephrasing... Find a subset of an array where the sum of elements is half the sum of the elements in the array.