## Amazon Interview Question

• 2

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

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++)
{
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])));
}
}``````

Comment hidden because of low score. Click to expand.
0

Since this algorithm gives us a polynomial time algorithm, it is very likely wrong.

Comment hidden because of low score. Click to expand.
0

So maybe you can prove this algorithm is wrong?
And, be the way, if you know polynomial solution for subset sum problem, tell it to me, I would be very grateful.

Comment hidden because of low score. Click to expand.
0

@Flux. WTF are you talking about?

You claim this works, giving a P time algorithm for an NP-Hard problem.

The burden of proof is on you, no?

Comment hidden because of low score. Click to expand.
0

If this is not P time, then carry on. Ignore stuff. etc etc.

Comment hidden because of low score. Click to expand.
0

@Anonymous, dude, my algorithm runs in exponentional time. Just look at signature

``rec = (index, cnt, sum) => ...``

Here index ranges from 0 to n-1, cnt from 1 to n and sum can have 2^n different values in worst case.
Total complexity is O(2^n * n^2).

Comment hidden because of low score. Click to expand.
0

Nice solution and analysis. Was very helpful for me. Thanks

Comment hidden because of low score. Click to expand.
1
of 1 vote

nice solution.

Looking at the base condition check, only check

``if (sum == 0) return cnt == 0;``

may not be enough.What if add

``if(cnt == 0) return sum == 0;``

before the first check? So we check both cnt == 0 case and sum == 0 case.

I could be wrong, ideas?

Comment hidden because of low score. Click to expand.
1
of 1 vote

Tested. with

``if(cnt == 0) return sum == 0;``

the processing speed is much faster than without it. I can paste log but it's too long. I have pasted my Java solution near the end. OP's algorithm works.

Comment hidden because of low score. Click to expand.
0

A = average of whole array
Create a subarray of size more than one where average is A.

Comment hidden because of low score. Click to expand.
0

My C++ implementation:

``````void EqualAverageDivide(vector<long>& data, vector<long> &left)
{
long sum = 0, P = 0;
size_t N = data.size(), K;
// Sort the data
std::sort(data.begin(), data.end());
for (vector<long>::const_iterator it = data.begin(); it != data.end(); it++)
sum += *it;
for (K = 1; K < (N - K); K++) {
if (((K * sum) % N)) //  check if such P can be integer (we operate with array of integers).
continue;
// picking K integers with sum of P from sorted array of integers
P = K * sum / N;
if (GetSum(data, K, P, 0, left))
break;
}
}

bool GetSum(vector<long> &data, size_t K, long P, size_t index, vector<long>& left)
{
if (!P)
return K == 0;
else if (!K)
return P == 0;
else if (index >= data.size())
return false;
for (size_t i = index; i < data.size(); i++) {
if (GetSum(data, K - 1, P - data[i], i + 1, left)) {
left.push_back(data[i]);
return true;
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

It seems easy but it actually is not. I would like it if you get some time and work it out.

Comment hidden because of low score. Click to expand.
0

High & Mighty XOR, posting your own problems and calling them bar raiser questions...

LOL.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

How do you know it was bar raiser?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How do you know it was bar raiser?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How do you know it was bar raiser?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How do you know it was bar raiser?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How do you know it was bar raiser?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How do you know it was bar raiser?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorting is not a solution

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//(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);

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

``````package com.cnu.ds;

import java.util.Queue;

public class DivideArray {
public static void name(int[] a) {
int sum1, sum2;
sum1 = a;
sum2 = 0;
boolean b = false;
for (int i = 1; i < a.length; i++) {
if (sum1 >= sum2 && a[i] > 0) {
sum2 += a[i];
} else {
sum1 += a[i];
}
}
int i = 0;
while (sum1 != sum2) {
if (sum1 > sum2) {
i = queue1.remove();
sum2 += i;
sum1 -= i;
} else if (sum1 < sum2) {
i = queue2.remove();
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 + " ");
}
}
}``````

Comment hidden because of low score. Click to expand.
0

boolean variable b is not required.

Comment hidden because of low score. Click to expand.
0

No it does not work !! try {1,2,3,4,5} gets caught in infinite loop

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 != arr)
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 = true;

if (!FindSubSet(arr, combination, 1, sum, arr, 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
case 2:
while (a.length > 1)
{
int S = a + a[\$-1];
if (P == S) return [a, 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.length > 0)
{
result ~= parts;
templ = parts ~ parts;
}
else
{
result ~= elem;
}
}
return result;
}

unittest
{
int[] a = [1, 7, 15, 29, 11, 9];
int[] templ = [9, 15];
auto tuple = divideByTemplate(a, templ);
assert(tuple == [15,9] && tuple == [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 && tuple)
{
writeln("One of the possible division for this array ", a, " is " , tuple, " and ", tuple, ". Avg for this ", AvgOfArray(tuple), " and ", AvgOfArray(tuple) );
}
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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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, a[i]);
int r = divide_impl(a + 1, llen + 1, rlen - 1, lsum + a, sum);
if (r >= 0) return r;
swap(a, 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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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("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) {

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
remove index: 0; number: 1
remove index: 1; number: 7
remove index: 2; number: 9
remove index: 3; number: 11
remove index: 4; number: 15
remove index: 5; number: 29
count: 2; sum: 24
remove index: 1; number: 7
remove index: 2; number: 9
remove index: 3; number: 11
remove index: 4; number: 15
remove index: 5; number: 29
remove index: 0; number: 1
remove index: 2; number: 9
remove index: 3; number: 11
remove index: 4; number: 15
remove index: 5; number: 29
remove index: 1; number: 7
remove index: 3; number: 11
9, 15``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{#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;
}

}}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

This is different thing....the question asked here and u rephrashing is different thing if u find a subset whose sum is just half of total sum it not necessary the avg of both side be same, if no of element in both side are same and sum also same then avg be same

Comment hidden because of low score. Click to expand.
0

You can transform this problem to the sum of a subset is zero by subtract the average from every element.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.