Last Updated: 22 Jul, 2022
Anuj and Subsets
Easy
Today is Anuj’s birthday and as he is fond of even numbers his friends gifted him with an array ‘ARR’ of ‘N’ positive integers.
Now being fond of even numbers he wanted to make a non-empty sequence out of the original array ‘ARR’, which only includes even numbers. To make the sequence he can delete any elements from the array and then concatenate the remaining elements in order.
But as he loves every even number equally he can’t decide which sequence to pick, Hence being his friend he asked you to find the count of sequences that only consists of even numbers so that he can make a detailed decision of which sequence to pick. Can you help him?
The answer can be very huge, so print the answer modulo 109+7.
EXAMPLE :
Input: ‘N’ = 3, ‘ARR’ = {2, 5, 8}
Output: 3
In this case, there are ‘3’ possible even sequences i.e. [2], [8], and [2, 8].
Input Format :
The first line will contain the integer ‘T’, the number of test cases.
Each test case consists of two lines.
The first line of input contains one integer, ‘N’, the length of the array ‘ARR’.
Followed by a line containing space-separated ‘N’ positive integers, denoting the elements of the array.
Output format :
For each test case, print the number of non-empty even sequences that can be formed by using the elements of the given array.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
1 <= ‘ARR[i]’ <= 10^9
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
Time Limit: 1 sec
Approaches
The idea for this approach is to iterate through each possible sequence with an even number and keep track of their count and in the end, return it.
To do this we can use a recursive approach, to find all the even sequences possible for the given array ‘ARR’ and increment the count of answers by one if we find a sequence that is not empty, as in our recursion we will never pick an odd element if at last, the sequence is not empty it will always have even elements.
Optimization: In place of ‘SUBSET’ you can also use a variable ‘COUNT’ representing the number of elements that are in the ‘SUBSET’ and increase ‘COUNT’ when inserting a new number and at the end, we increase our answer if ‘COUNT’ is greater than 0.
Algorithm:
// This function will generate all possible sequences possible for the given array.
Void getSubsets(i, SUBSET, ANS, N, ARR)
- If ‘i==N’
- Initialize the variable ‘SIZE’ with the value of the length of the list ‘SUBSET’.
- Initialize the variable ‘MOD’ with the value of ‘109+7’.
- If ‘SIZE != 0’
- Increment ‘ANS’ by ‘1’.
- Assign ‘ANS’ the value of the remainder of the division of ‘ANS’ by ‘MOD’.
- Return.
- Call ‘getSubsets(i+1, SUBSET, ANS, N, ARR)’.
- If ‘ARR[i]’ is even
- Insert ‘ARR[i]’ at the end of the list ‘SUBSET’.
- Call ‘getSubsets(i+1, SUBSET, ANS, N, ARR)’.
- Remove the last element of the ‘SUBSET’.
- Return.
// The function will return the count of non-empty even sequences of the given array ‘ARR’.
Int evenSubsets(N, ARR)
- Initialize the variable ‘ANS’ with the value of ‘0’.
- Initialize an empty list ‘SUBSET’.
- Call ‘getSubsets(0, SUBSET, ANS, N, ARR)’.
- Return ‘ANS’.
The idea for this approach is to first find the count of even elements of the array ‘ARR’ and using that we can calculate the even sequences using the formula of ‘2count of even - 1’.
Now the above formula can be derived in the following way:
Let’s suppose there are ‘X’ even elements, then for each even element, there is the possibility that either it is included in the sequence or not, thus it leads to the ‘2’ possibility for each of the elements.
Hence the total possibilities become ‘2X’. But that will also include the possibility where none of the elements is picked thus it should be removed from the total count. Thus the formula for all possible non-empty even sequences is ‘2X - 1’.
Algorithm:
// The function will return the count of non-empty even sequences of the given array ‘ARR’.
Int evenSubsets(N, ARR)
- Initialize the variable ‘COUNT’ with the value of ‘0’.
- Initialize the variable ‘MOD’ with the value of ‘109+7’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- If ‘ARR[i]’ is even
- Increment ‘COUNT’ by ‘1’.
- If ‘ARR[i]’ is even
- Initialize the variable ‘ANS’ with the value of ‘1’.
- Run a for loop from ‘1’ to ‘COUNT’ with a variable named ‘i’.
- Multiply ‘ANS’ by ‘2’.
- Assign ‘ANS’ the value of the remainder of the division of ‘ANS’ by ‘MOD’.
- Decrement ‘ANS’ by ‘1’.
- Return ‘ANS’