top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

How to divide an array into two parts so that average of both the arrays are equal?

+3 votes
363 views

Input:
[1 7 15 29 11 9]

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

Average of first part: (15+9)/2 = 12,
Average of second part: (1 + 7 + 11 + 29) / 4 = 12

posted Oct 12, 2015 by anonymous

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

1 Answer

0 votes

NOTE 1: If a solution exists, you should return a list of exactly 2 lists of integers A and B which follow the following condition :
* numElements in A <= numElements in B
* If numElements in A = numElements in B, then A is lexicographically smaller than B ( https://en.wikipedia.org/wiki/Lexicographical_order )

NOTE 2: If multiple solutions exist, return the solution where length(A) is minimum. If there is still a tie, return the one where A is lexicographically smallest.

NOTE 3: Array will contain only non negative numbers.

assume the two sets are set1 and set2.

Assume sum of set1 = Sum_of_Set1, with size = size_of_set1.
Assume sum of set2 = Sum_of_Set2, with size = size_of_set2

SUM_of_Set1 / size_of_set1 = SUM_of_Set2 / size_of_set2
SUM_of_Set1 = SUM_of_Set2 * (size_of_set1 / size_of_set2)

total_sum = Sum_of_Set1 + Sum_of_Set2
AND size_of_set2 = total_size - size_of_set1

Sum_of_Set1 = (total_sum - Sum_of_Set1) * (size_of_set1 / (total_size - size_of_set1))
OR on simplifying,

total_sum / Sum_of_Set1 - 1 = (total_size - size_of_set1) / size_of_set1
total_sum / Sum_of_Set1 = total_size / size_of_set1
Sum_of_Set1 / size_of_set1 = total_sum / total_size

Note that you need the solution with minimum size_of_set1 if multiple solutions exist.
So, just iterate on size_of_set1.
Based on size_of_set1, you can determine the value of Sum_of_Set1.

Then after you can memoise this relation -

isPossible(ind, current_sum, current_size) =

isPossible(ind + 1, current_sum, current_size) [ Do not include current element ]
OR
isPossible(ind + 1, current_sum - value_at(ind), current_size - 1)

vector<vector<vector<bool> > > dp;
vector<int> res;
vector<int> real;
int total;

bool isPossible(int idx, int sum, int len)
{
    if (len == 0) return (sum == 0);
    if (idx >= total) return false;

    if (dp[idx][sum][len] == false) return false;

    if (sum >= real[idx])
    {
        res.push_back(real[idx]);
        if (isPossible(idx + 1, sum - real[idx], len - 1)) return true;
        res.pop_back();
    }

    if (isPossible(idx + 1, sum, len)) return true;

    return dp[idx][sum][len] = false;
}

vector<vector<int> > avgset(vector<int> arr) 
{
    sort(arr.begin(), arr.end());
    real.clear();
    real = arr;
    dp.clear();
    res.clear();

    int total_sum = 0;
    total = arr.size();

    for(int i = 0; i < total; ++i)
        total_sum += arr[i];

    dp.resize(real.size(), vector<vector<bool> > (total_sum + 1, vector<bool> (total, true)));

    // We need to minimize size_of_set1. So, lets search for the first size_of_set1 which is isPossible. 
    for (int i = 1; i < total; i++)
    {
        // Sum_of_Set1 has to be an integer
        if ((total_sum * i) % total != 0) continue;
        int Sum_of_Set1 = (total_sum * i) / total;
        if (isPossible(0, Sum_of_Set1, i))
        {
            // Ok. Lets find out the elements in arr, not in res, and return the result.
            int ptr1 = 0, ptr2 = 0;
            vector<int> res1 = res;
            vector<int> res2;
            while (ptr1 < arr.size() || ptr2 < res.size())
            {
                if (ptr2 < res.size() && res[ptr2] == arr[ptr1])
                {
                    ptr1++;
                    ptr2++;
                    continue;
                }
                res2.push_back(arr[ptr1]);
                ptr1++;
            }

            vector<vector<int> > ans;
            ans.push_back(res1);
            ans.push_back(res2);
            return ans;
        }
    }

    vector<vector<int> > ans;
    return ans;
}
answer Oct 19, 2015 by Mohammed Hussain
Similar Questions
+8 votes

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

+3 votes

Given an active stream of sorted arrays, how would you merge them efficiently?
C or Java code would be helpful?

+7 votes

Given two n-node trees, how many rotations does it take to convert one tree into the other?

0 votes

Write a c program that rotate elements of an array by the value of configured number "n".
For example:
Input array[ ] = { 2, 3, 5, 6, 8, 9}
value of n = 2
Output array[] = { 5, 6, 8, 9, 2, 3}
I am looking for efficient program.

+5 votes

Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...