City of Happy People

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
25 upvotes
Asked in companies
NXP SemiconductorsShell indiaD.E.Shaw

Problem statement

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’?

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 1 1 
1 2
3 -1 1
-1 1 2
Sample Output 1 :
1
5
Explanation For Sample Output 1 :
For sample test case 1 : 

Given ‘HAPPINESS[]’ = [1,2] , and ‘A’, and ‘B’ are 1 and 1 respectively. Following are all the possible groups with their overall happiness value:

1. [1, 2], where the overall happiness value is 3.

2. [1], where the overall happiness value is 1.

3. [2], where the overall happiness value is 2.

4. [ ], where the overall happiness value is 0.

As we can see, there is only 1 way to make a group in which overall happiness value lies between 1 and 1 inclusive that is [1].


For sample test case 2 : 

Given ‘HAPPINESS[]’ = [-1,1,2] ,‘A’, and ‘B’ are -1 and 1 respectively. Following are all the possible groups with their overall happiness value:

1. [-1], where the overall happiness value is -1.

2. [1], where the overall happiness value is 1.

3. [2], where the overall happiness value is 2.

4. [-1,1], where the overall happiness value is 0.

5. [-1,2], where the overall happiness value is 1.

6. [1,2], where the overall happiness value is 3.

7. [-1,1,2], where the overall happiness value is 0.

As we can see there are 5 ways to make a group in which overall happiness value lies between -1 and 1 inclusive and that are  [-1], [1], [-1,1],  [-1,2], [-1,1,2].
Sample Input 2 :
2
3 -10 10
1 3 5
2 -4 -1 
2 3
Sample Output 2 :
8
0
Hint

Try to use a brute force approach in this problem

Approaches (2)
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’.
Time Complexity

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)).

Space Complexity

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).

Code Solution
(100% EXP penalty)
City of Happy People
Full screen
Console