City of Happy People
Ninja is traveling to a Happy city where ‘N’ people reside. In the city, the happiness of each person is represented as a number ‘H’ where ‘H’ ranges from -20,000,000 to 20,000,000 (both inclusive). The happiness of each person in the city is given in an array/list ‘HAPPINESS’ where ‘HAPPINESS[i]’ represents the happiness of the i’th person.

Ninja wants to make a group of people such that the overall happiness of the group (sum of happiness value of all the people in the group) ranges between ‘A’ and ‘B’ where -500,000,000 ≤ A ≤ B ≤ 500,000,000. Ninja wants to know in how many ways he can make this group.

For example :

For the given ‘HAPPINESS[]’ = ‘[-1, 0, 3]’ and ‘A’ = 0 , ‘B’ = 2. Following are the ways to group people such that the overall happiness of the group is between ‘A’ and ‘B’: [-1, 0, 3], the sum of all the happiness values of this group is 2. [-1, 3], the sum of all the happiness values of this group is 2. [0], the sum of all the happiness values of this group is 0. [ ], the sum of all the happiness values of this empty group is 0. So the number of ways is 4.

As Ninja is busy with some other task so he asks you for help. Can you help Ninja to find out the number of ways in which he can pick groups so that the overall happiness of the group must be in the range between ‘A’ and ‘B’?

Input Format :

The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains three single space-separated integers ‘N’, ’A’, and ‘B’ representing the number of elements in the array/list ‘HAPPINESS’ and the range in which happiness values of groups must reside respectively. The next line of each test case contains ‘N’ single space-separated integers denoting the ‘HAPPINESS’ values.

Output Format :

For each test case, print the number of ways to pick groups so that the overall happiness of the group lies between ‘A’ and ‘B’ inclusive. Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1

Question

City of Happy People

Ninja is traveling to a Happy city where ‘N’ people reside. In the city, the happiness of each person is represented as a number ‘H’ where ‘H’ ranges from -20,000,000 to 20,000,000 (both inclusive). The happiness of each person in the city is given in an array/list ‘HAPPINESS’ where ‘HAPPINESS[i]’ represents the happiness of the i’th person.

Ninja wants to make a group of people such that the overall happiness of the group (sum of happiness value of all the people in the group) ranges between ‘A’ and ‘B’ where -500,000,000 ≤ A ≤ B ≤ 500,000,000. Ninja wants to know in how many ways he can make this group.

For example :

For the given ‘HAPPINESS[]’ = ‘[-1, 0, 3]’ and ‘A’ = 0 , ‘B’ = 2. Following are the ways to group people such that the overall happiness of the group is between ‘A’ and ‘B’:

[-1, 0, 3], the sum of all the happiness values of this group is 2.

[-1, 3], the sum of all the happiness values of this group is 2.

[0], the sum of all the happiness values of this group is 0.

[ ], the sum of all the happiness values of this empty group is 0.

So the number of ways is 4.

As Ninja is busy with some other task so he asks you for help. Can you help Ninja to find out the number of ways in which he can pick groups so that the overall happiness of the group must be in the range between ‘A’ and ‘B’?

Input Format :

The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains three single space-separated integers ‘N’, ’A’, and ‘B’ representing the number of elements in the array/list ‘HAPPINESS’ and the range in which happiness values of groups must reside respectively.

The next line of each test case contains ‘N’ single space-separated integers denoting the  ‘HAPPINESS’ values.

Output Format :

For each test case, print the number of ways to pick groups so that the overall happiness of the group lies between ‘A’ and ‘B’ inclusive.

Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 100
1 <= ‘N’ <= 34
-20,000,000 ≤ ‘HAPPINESS[i]’ ≤ 20,000,000
-500,000,000 ≤ ‘A’ ≤ ‘B’ ≤ 500,000,000

Time Limit: 1 second

Accepted Answer

The problem is to find the number of ways to form a group of people such that the overall happiness of the group falls within a given range.

Iterate through all possible subsets of the given array/list
Calculate the sum of happiness values for each subset
Count the number of subsets whose sum falls within the given range

Accepted Answer

Brute Force

We know there are a total 2 ^ ‘N’ subsets possible for an array/list of ‘N’. elements. The idea behind this approach is to generate all possible subsets and then find the sum of all the happiness values in each subset. If this sum lies in between the range ‘A’ to ‘B’ (both inclusive) then include it in our final answer.

Here is the complete algorithm:

Initialize a variable ‘answer’ that will be our final result.
Initialize a variable ‘sum’ = 0 and for each number ‘i’ from 0 to 2 ^ ‘N’, pick all array elements which corresponds to 1 in the binary representation of the ’i’ and add this element to the sum.
Check if the sum lies between ‘A’ to ‘B’ then add this to our ‘answer’.
Finally, return ‘answer’.

Space Complexity: O(1)Explanation:

O(1), Where N is the number of happiness values in ‘HAPPINESS’.

Because we are not using any extra space. Hence overall space complexity is O(1).

Time Complexity: O(2^n)Explanation:

O(2 ^ (N)), Where N is the number of happiness values in ‘HAPPINESS’.

Because we are generating all the subsets for the array/list of size ‘N’. Hence the overall time complexity will be O(2 ^ (N)).

Accepted Answer

Binary Search & Bit masking

We can optimize the previous approach. In the brute force approach, there will be 2^34 (17179869184) subsets in the worst case. We can reduce this problem by dividing the ‘HAPPINESS’ into two sets [0…’N / 2’] and [‘N / 2’…’N - 1’] and find all subsets individually.

Now we can find all the combinations of these sets giving the sum in the desired range. This can also be done in an optimized way, We need to sort one of the set ‘SET_A’ or ‘SET_B’ where as ‘SET_A’ contains subset sum of each subset from index 0 to ‘N’ / 2 of the ‘HAPPINESS’ and ‘SET_B’ contains subset sum of each subset from index ‘N’ / 2’ to ‘N’ of the ‘HAPPINESS’ .We will use binary search so that the values from one set that will turn out the sum for the particular value of the other set.

For Example:

We have ‘N’ = 4, ‘A’ = -1 ,‘B’ = 1 and ‘HAPPINESS’ = [1, 2, -1, 0].

Set of all the subset sums of ‘HAPPINESS’ for 0 to ‘N’ / 2 is ‘SET_A’ and for ‘N’ / 2 to ‘N’ - 1 is ‘SET_B’.

We obtain these two sets like ‘SET_A’ = [0,1, 2, 3] and ‘SET_B’ = [-1, -1, 0, 0] which contains all the possible happiness values. Now for each value in the 'SET_A' we will use the binary search algorithm for finding the values that would produce our desired sum using this approach we can get the total sets that yield the sum between 'A' and 'B'.

Here is the complete algorithm:

Initialize a variable ‘answer’ = 0 to store the final result. We make two arrays/lists ‘left’ and ‘right’ to store the result of two halves [0…’N / 2’] and [‘N / 2’…’N - 1’] of ‘HAPPINESS’. We will call our helper function ‘generateSubsets’ and store the resulting array/list in ‘left’ and ‘right’ respectively.
Here is the algorithm for ‘generateSubsets’ is:
- Initialize a variable ‘sum’ = 0.
- For ‘i’ = 0 to ‘i’ = 2 ^ ‘N’ do the following:
  - Iterate all the bits of ‘i’ and do the following:
    - If the bit is set then add that value to ‘sum’.
  - Finally, insert ‘sum’ into an array/list.
Sort the ‘right’ array/list in increasing order.
Iterate the ‘left’ array/list and for each element at index ‘i’ do the following:
- Find out the position of the smallest element which is greater than or equal to ‘A’ - ‘left[i]’ using ‘lowerBound’ function and store it in a variable ‘low’.
- Find out the position of the smallest element which is greater than ‘A’ - ‘left[i]’ using ‘upperBound’ and store it in a variable ‘high’.
- Update ‘answer’ as ‘answer’ = ‘answer’ + (‘high’-’right.begin()’)-(‘low’-’right.begin()’)
Finally, return ‘answer’

Here is the algorithm for ‘lowerBound’ function:

This algorithm is used to find the position of the minimum element in a sorted array ‘HAPPINESS’ that is greater than or equal to ‘X’
Initialize two variables ‘low’ = 0 and ‘high’ = ‘N’.Do the following while ‘low’ is less than ‘high’.
- Initialize ‘mid’ = (‘low’ + ‘high’) / 2.
- If ‘X’ <= ‘HAPPINES[mid]’ then ‘high’ = ‘mid’.
- Else ‘low’ = ‘mid’ + 1.
Finally, return ‘low’.

Here is the algorithm for ‘upperBound’ function:

This algorithm is used to find the position of the minimum element in a sorted array ‘HAPPINESS’ that is greater than ‘X’.
Initialize two variables ‘low’ = 0 and ‘high’ = ‘N’.Do the following while ‘low’ is less than ‘high’.
- Initialize ‘mid’ = (‘low’ + ‘high’) / 2.
- If ‘X’ >= ‘HAPPINES[mid]’ then ‘low’ = ‘mid’ + 1.
- Else ‘high’ = ‘mid’.
Finally, return ‘low’.

Space Complexity: OtherExplanation:

O(2 ^ (N/2)), Where N is the number of happiness values in ‘HAPPINESS’.

Because in the worst case the ‘left’ and ‘right‘ array/list will be containing subsets sum of ‘N’ / 2 subsets. Hence the overall time complexity will be O(2 ^ (N/2)).

Time Complexity: OtherExplanation:

O(N * 2 ^ (N/2)), Where N is the number of happiness values in ‘HAPPINESS’.

Because we are generating all the subsets for the subarrays of size ‘N’ / 2 and finally using binary search on size 2 ^ (‘N’ / 2) subset sums. Approximate operations would be of 2^17+sort(2^16)+2^17 order. Hence overall time complexity will be O(N * 2 ^ (N/2)).

Java (SE 1.8)

/*



    Time Complexity : O(N * 2 ^ (N/2))

    Space Complexity : O(2 ^ (N/2))



    Where N is the number of persons in the city.



*/



import java.util.ArrayList;

import java.util.Arrays;



public class Solution 

{

    // To find lower bound of a value in the array.

    public static int lowerBound(int[] happiness, int n, int x) 

    {

        int low = 0, high = n;



        while (low < high) 

        {



            int mid = (low + high) / 2;

            if (x <= happiness[mid]) 

            {

                high = mid;

            } 

            else 

            {

                low = mid + 1;

            }

        }

        return low;

    }



    // To find upper bound of a value in the array.

    public static int upperbound(int[] happiness, int n, int x) 

    {

        int low = 0, high = n;



        while (low < high) 

        {

            int mid = (low + high) / 2;

            if (x >= happiness[mid]) 

            {

                low = mid + 1;

            } 

            else 

            {

                high = mid;

            }

        }

        return low;

    }



    // To find all subsets.

    public static void generateSubsets(int start, int num, ArrayList happiness, int[] arr) 

    {

        int sum;

        for (int i = 0; i < (1 << num); ++i) 

        {

            sum = 0;

            for (int j = 0; j < num; j++) 

            {

                if ((i & (1 << j)) > 0) 

                {

                    sum = sum + happiness.get(j + start);

                }

            }

            arr[i] = sum;

        }

    }



    public static int makeHappyGroup(ArrayList happiness, int n, int a, int b) 

    {

        int answer = 0;

        int[] left, right;

        int low, high;



        int num = n / 2;

        left = new int[(1 << num)];



        // Generate all subsets store in the left array.

        generateSubsets(0, n / 2, happiness, left);



        if (n % 2 == 1) 

        {

            num = n / 2 + 1;

            right = new int[(1 << num)];



            // Generate all subsets store in the right array.

            generateSubsets(n / 2, n / 2 + 1, happiness, right);

        } 

        else 

        {

            num = n / 2;

            right = new int[(1 << num)];



            // Generate all subsets store in the right array.

            generateSubsets(n / 2, n / 2, happiness, right);

        }



        // Sort the array.

        Arrays.sort(right);



        for (int i = 0; i < left.length; ++i) 

        {

            low = lowerBound(right, right.length, a - left[i]);

            high = upperbound(right, right.length, b - left[i]);

            answer = answer + (high - low);

        }



        return answer;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity : O(N * 2 ^ (N/2))
    Space Complexity : O(2 ^ (N/2))

    Where N is the number of persons in the city.

*/

#include 

// To find lower bound of a value in the array.
int lowerBound(vector &happiness, int n, int x)
{
    int low = 0, high = n;

    while (low < high)
    {

        int mid = (low + high) / 2;
        if (x <= happiness[mid])
        {
            high = mid;
        } else
        {
            low = mid + 1;
        }
    }
    return low;
}

// To find upper bound of a value in the array.
int upperbound(vector &happiness, int n, int x)
{
    int low = 0, high = n;

    while (low < high)
    {
        int mid = (low + high) / 2;
        if (x >= happiness[mid])
        {
            low = mid + 1;
        } else
        {
            high = mid;
        }
    }
    return low;
}

// To find all subsets.
void generateSubsets(int start, int num, vector &happiness, vector &arr)
{
    int sum;
    for (int i = 0; i < (1 << num); ++i)
    {
        sum = 0;
        for (int j = 0; j < num; j++)
        {
            if (i & (1 << j))
            {
                sum = sum + happiness[j + start];
            }
        }
        arr.push_back(sum);
    }
}

int makeHappyGroup(vector &happiness, int n, int a, int b)
{
    int answer = 0;
    vector left, right;
    int low, high;

    // Generate all subsets store in the left array.
    generateSubsets(0, n / 2, happiness, left);

    if (n % 2 == 1)
    {
        // Generate all subsets store in the right array.
        generateSubsets(n / 2, n / 2 + 1, happiness, right);
    }
    else
    {
        // Generate all subsets store in the right array.
        generateSubsets(n / 2, n / 2, happiness, right);
    }

    // Sort the array
    sort(right.begin(), right.end());

    for (int i = 0; i < left.size(); ++i)
    {
        low = lowerBound(right, right.size(), a - left[i]);
        high = upperbound(right, right.size(), b - left[i]);
        answer = answer + (high - low);
    }

    return answer;
}

Python (3.5)

'''

    Time Complexity : O(N * 2 ^ (N/2))
    Space Complexity : O(2 ^ (N/2))

    Where N is the number of persons in the city.

'''

# To find lower bound of a value in the array.
def lowerBound(happiness :list, n :int, x :int):
    low, high = 0, n

    while low < high:

        mid = (low + high) // 2
        if (x <= happiness[mid]):
            high = mid
        else:
            low = mid + 1
    return low

# To find upper bound of a value in the array
def upperbound(happiness :list, n :int, x :int):
    low, high = 0, n

    while low < high:
        mid = (low + high) // 2
        if (x >= happiness[mid]):
            low = mid + 1
        else:
            high = mid
        
    return low

# To find all subsets.
def generateSubsets(start :int, num :int, happiness :list, arr :list):
    for i in range(1 << num):
        sum = 0
        for j in range(num):
            if (i & (1 << j)):
                sum = sum + happiness[j + start]
            
        arr.append(sum)

def makeHappyGroup(happiness :list, n :int, a :int, b :int):
    answer = 0
    left, right = [], []
    low, high = 0, 0

    # Generate all subsets store in the left array.
    generateSubsets(0, n // 2, happiness, left)

    if (n % 2 == 1):
        # Generate all subsets store in the right array
        generateSubsets(n // 2, n // 2 + 1, happiness, right)
    else:
        # Generate all subsets store in the right array
        generateSubsets(n // 2, n // 2, happiness, right)

    # Sort the array
    right.sort()

    for i in range(len(left)):
        low = lowerBound(right, len(right), a - left[i])
        high = upperbound(right, len(right), b - left[i])
        answer = answer + (high - low)

    return answer