Anuj and Subsets

Easy
0/40
Average time to solve is 15m
profile
Contributed by
0 upvote

Problem statement

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
1 2 3 4 5
5
3 2 2 1 6
Sample Output 1 :
3
7
Explanation Of Sample Input 1 :
For the first test case, the even elements of the array ‘ARR’ are [2, 4]. Hence the non-empty even sequences are - [2], [4], [2, 4].

Hence, the output will be: 3

For the second test case, the even elements of the array ‘ARR’ are [2, 2, 6]. Hence the non-empty even sequences are - [2], [2], [6], [2, 2], [2, 6], [2, 6], [2, 2, 6].

Hence, the output will be: 7
Sample Input 2 :
2
10
16 4 12 6 10 2 18 2 14 20
8
1 5 3 9 7 5 3 11
Sample Output 2 :
1023
0
Hint

Can we try to make all possible even sequences?.

Approaches (2)
Brute Force

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’.
Time Complexity

O( 2 ^ N ), Where ‘N’ is the input integer.

In the above recursive approach, we iterate through each possible even sequence, and in the worst case all elements of the array ‘ARR’ can be even, hence there will be ‘2^N’ possibilities. 

Hence the time complexity will be O( 2 ^ N ).

Space Complexity

O( N ), Where ‘N’ is the input integer.

 

In the above recursive approach, in the worst case when all elements of the array ‘ARR’ are even, there can be at most ‘N’ recursive calls of the function ‘getSubsets’ which will use a recursion stack of ‘N’ and we also use the list ‘SUBSET’ whose length will be ‘N’ in this case.

Hence the space complexity will be O( N ).

Code Solution
(100% EXP penalty)
Anuj and Subsets
Full screen
Console