Last Updated: 12 Nov, 2020
Number of Subsequences with Even and Odd Sum
Moderate
Asked in companies
You are given an array consisting of 'N' positive integers, and your task is to find the number of subsequences with odd sum and the number of subsequences with even sum. As the numbers can be too large, you need to return both the numbers mod 10 ^ 9 + 7.
A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, consider the array {1, 2, 3}, there are 7 possible subsequences for this. They are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.
Even sum subsequence means the subsequence whose total sum( sum of all the elements in the subsequence) is divisible by 2. And for odd sum subsequence, the total sum leaves a remainder of 1 when divided by 2.
Note:
1) In general, for an array of size 'N', there are (2 ^ 'N' - 1) non-empty subsequences possible. Because we are not considering empty subsequence for this problem.
2) The array may contain duplicate elements.
3) X mod 10 ^ 9 + 7 is the remainder when X is divided by 10 ^ 9 + 7.
Input Format:
The first line of input contains the integer 'T', denoting the number of test cases.
The first line of each test case contains an integer 'N', denoting the size of the array.
The second line of each test case contains 'N' space-separated integers denoting the array elements.
Output Format:
For each test case, return two space-separated integers X and Y, the number of subsequences with even sum and the number of subsequences with odd sum respectively. Remember both the numbers need to be returned mod 10^9 + 7.
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 <= 10^4
1 <= ARR[i] <= 10^9
Where 'ARR[i]' denotes the array elements.
Time limit: 1 sec
Approaches
- This problem can be solved using recursion. And the idea behind this is to generate all the possible subsequence sum from the given set.
- For each element, we will have two choices: either to include it in the first subset or not. So, at each stage, we will make two recursive calls, one which will consider including the current element and other which won’t. We will explore the depth taking into consideration each of the two possible cases.
- When we have no elements to explore we will check if the sum calculated along this path is odd we will add the count for the number of subsequences with the odd sum, otherwise, we will add the count for even sum.
- The main idea behind this approach is that sum of two odd numbers is odd, the sum of two even numbers is even and the sum of one even and one odd number is odd.
- With this idea, we can approach the solution by maintaining two DP’s one for odd sum and one for even sum.
- ‘ODD[i]', represents the number of subsequences with the odd sum in range (0 to I), and ‘EVEN[i]’ represents the number of subsequences with even sum in range (0 to i).
- Now we run a loop through all the elements:
- If the element being traversed is an odd integer then:
- ‘ODD[i]’ = ‘ODD[i-1]’ + ‘EVEN[i-1]’ + 1 (because even + odd gives odd, so if we add this odd number to all the even sum subsequences till i-1th element then we will get the subsequence with odd sum).
- And ‘EVEN[i]’ = ‘EVEN[i-1]’ + ‘ODD[i-1]’ (because odd + odd gives even, so if we add this odd number to all the odd sum subsequences till i-1th element then we will get the subsequence with even sum).
- If the element being traversed is an even integer then:
- ‘ODD[i]’ = ‘ODD[i-1]’ + ‘ODD[i-1]’ (because even + odd gives odd, so if we add this even number to all the odd sum subsequences till i-1th element then we will get the subsequence with odd sum).
- And ‘EVEN[i]’ = ‘EVEN[i-1]’ + ‘EVEN[i-1]’ + 1 (because even + even gives even, so if we add this even number to all the even sum subsequences till i-1th element then we will get the subsequence with even sum).
- After each step of calculation( adding two numbers) we will take mod with 1000000007, because at any step the count may go beyond the range.
- After the end of all the above calculations, ‘ODD[N]’, and ‘EVEN[N]’ will be our answer, where ‘N’ is the number of elements in the array.
- The main idea behind this approach is that our dp value at any state ‘i’ is only dependent on the value at the state ‘i-1’. So we need not store all the states. Instead, we can have two variables to keep track of the present and previous state of the odd sum and two variables to keep track of the present and the prior state of the even sum.
- Before starting with the loop we have initialized four variables named ‘ODDPREVIOUS’, ‘ODDPRESENT’, ‘EVENPREVIOUS’, and ‘EVENPRESENT’ to keep track of the states as explained in the above point.
- Now we run a loop through all the elements:
- If the element being traversed is an odd integer then:
- ‘ODDPRESENT’ = ‘ODDPREVIOUS’ + ‘EVENPREVIOUS’ + 1 (because even + odd gives odd, so if we add this odd number to all the even sum subsequences till i-1th element then we will get the subsequence with odd sum).
- And ‘EVENPRESENT’ = ‘EVENPREVIOUS’ + ‘ODDPREVIOUS’ (because odd + odd gives even, so if we add this odd number to all the odd sum subsequences till i-1th element then we will get the subsequence with even sum).
- If the element being traversed is an even integer then:
- ‘ODDPRESENT’ = ‘ODDPREVIOUS’ + ‘ODDPREVIOUS’(because even + odd gives odd, so if we add this even number to all the odd sum subsequences till i-1th element then we will get the subsequence with odd sum).
- And ‘EVENPRESENT’ = ‘EVENPREVIOUS’ + ‘EVENPREVIOUS’ + 1 (because even + even gives even, so if we add this even number to all the even sum subsequences till i-1th element then we will get the subsequence with even sum).
- After the end of all the above calculations, ‘ODDPRESENT’, and ‘EVENPRESENT’ will be our answers.
Similar problems