Problem

Submissions

Hints & solutions

Discuss

Number of Subsequences with Even and Odd Sum

Moderate

0/80

Average time to solve is 25m

Contributed by

1 upvote

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

1
3
1 2 3

Sample Output 1:

3 4

Explanation for Sample Output 1:

The number of subsequences with an even sum is 3, and the number of subsequences with an odd sum is 4.

The possible subsequences are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. And their sums are 1,2,3,3,4,5 and 6 respectively. So there are 3 subsequence with even sum and 4 subsequence with odd sum.

Sample Input 2:

1
32
36 21 23 33 25 22 22 4 16 39 4 27 20 22 40 38 18 35 21 7 31 10 7 10 19 11 5 39 41 36 14 9

Sample Output 2:

147483633 147483634

Hint 1

Hint 2

Hint 3

Try generating all the possible subsequences.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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.

Time Complexity

O(2 ^ N), Where 'N' is the number of elements in the array.

Since we are considering each subsequence of the array which takes O(2 ^ N) time. Thus the time complexity will be O(2 ^ N).

Space Complexity

O(N), Where ‘N’ is the number of elements in the array.

Since in case of recursion the space complexity is proportional to the depth of the recursion tree, which in this case is proportional to the number of elements in the array. Thus the space complexity will be O(N).

(100% EXP penalty)

Number of Subsequences with Even and Odd Sum

Console