Number of Subsequences with Even and Odd Sum

0 0 11 minutes read

Given an array, find the number of subsequences whose sum is even and the number of subsequences whose sum is odd.

Example:

Input: arr[] = {1, 2, 2, 3}
Output: EvenSum = 7, OddSum = 8
There are $2^{N}-1$ possible subsequences.
The subsequences with even sum is
1) {1, 3} Sum = 4
2) {1, 2, 2, 3} Sum = 8
3) {1, 2, 3} Sum = 6 (Of index 1)
4) {1, 2, 3} Sum = 6 (Of index 2)
5) {2} Sum = 2 (Of index 1)
6) {2, 2} Sum = 4
7) {2} Sum = 2 (Of index 2)
and the rest subsequence is of odd sum.

Input: arr[] = { 2, 2, 2, 2 }
Output: EvenSum = 15, OddSum = 0

Naive Approach:
One simple approach is to generate all possible subsequences recursively and count the number of subsequences with an even sum and then subtract from total subsequences and the number will be of odd subsequence. The time complexity of this approach will be $O(2^{N})$ .

Better Approach:
A better approach will be using Dynamic programming.

We would be calculating the count of even subsequences as we iterate through the array. we create 2 arrays countODD[N] and countEVEN[N], where countODD[i] denotes the number of subsequences with odd sum in range $(0, i)$ and countEVEN[i] denotes the number of subsequences with even sum in range $(0, i)$
If we are at position i, and the number is ODD then the total number of subsequences with an even sum would be
- For countEVEN[i], the i-th number is not paired with any other subsequence (i.e. even subsequences till $(i-1)$ position) + ith number is paired with all other odd subsequences till $(i-1)$ position (odd+odd=even)
- For countODD[i], the i-th number is not paired with any other subsequence(i.e. odd subsequences till $(i-1)$ position) + ith number is paired with all other even subsequences till $(i-1)$ position (odd+even=odd) + one subsequence with only 1 element i.e the ith number itself
If we are at position i, and the number is EVEN then the total number of subsequences with an even sum would be
- For countEVEN[i], the i-th number is not paired with any other subsequence (i.e. even subsequences till $(i-1)$ position) + i-th number is paired with all other even subsequences till $(i-1)$ position (even+even=even) + one subsequence with only 1 element i.e the i-th number itself
- For countODD[i], the i-th number is not paired with any other subsequence (i.e. odd subsequences till $(i-1)$ position) + i-th number is paired with all other odd subsequences till $(i-1)$ position (even+odd=odd)

Below is the implementation of above approach:

C++

// C++ implementation
#include <bits/stdc++.h>
using namespace std;
 
// returns the count of odd and
// even subsequences
pair<int, int> countSum(int arr[], int n)
{
    int result = 0;
 
    // Arrays to store the count of even
    // subsequences and odd subsequences
    int countODD[n + 1], countEVEN[n + 1];
 
    // Initialising countEVEN[0] and countODD[0] to 0
    // since as there is no subsequence before the
    // iteration with even or odd count.
    countODD[0] = 0;
    countEVEN[0] = 0;
 
    // Find sum of all subsequences with even count
    // and odd count storing them as we iterate.
 
    // Here countEVEN[i] denotes count of
    // even subsequences till i
 
    // Here countODD[i] denotes count of
    // odd subsequences till i
 
    for (int i = 1; i <= n; i++) {
 
        // if the number is even
        if (arr[i - 1] % 2 == 0) {
            countEVEN[i] = countEVEN[i - 1]
                           + countEVEN[i - 1] + 1;
 
            countODD[i] = countODD[i - 1]
                          + countODD[i - 1];
        }
        // if the number is odd
        else {
            countEVEN[i] = countEVEN[i - 1]
                           + countODD[i - 1];
 
            countODD[i] = countODD[i - 1]
                          + countEVEN[i - 1] + 1;
        }
    }
 
    return { countEVEN[n], countODD[n] };
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Calling the function
 
    pair<int, int> ans = countSum(arr, n);
 
    cout << "EvenSum = " << ans.first;
    cout << " OddSum = " << ans.second;
 
    return 0;
}

Java

// Java implementation to find the number 
// of Subsequences with Even and Odd Sum 
import java.util.*; 
import java.lang.*;
 
class GFG 
{
    public static int[] countSum(int arr[], int n)
    {
        int result = 0; 
 
        // Arrays to store the count of even 
        // subsequences and odd subsequences 
        int[] countODD = new int[n + 1];
        int[] countEVEN = new int[n + 1];
         
        // Initialising countEVEN[0] and countODD[0] to 0 
        // since as there is no subsequence before the 
        // iteration with even or odd count. 
        countODD[0] = 0; 
        countEVEN[0] = 0; 
         
        // Find sum of all subsequences with even count 
        // and odd count storing them as we iterate. 
     
        // Here countEVEN[i] denotes count of 
        // even subsequences till i 
     
        // Here countODD[i] denotes count of 
        // odd subsequences till i 
        for (int i = 1; i <= n; i++) 
        { 
 
            // if the number is even 
            if (arr[i - 1] % 2 == 0)
            { 
                countEVEN[i] = countEVEN[i - 1] + 
                               countEVEN[i - 1] + 1; 
     
                countODD[i] = countODD[i - 1] + 
                              countODD[i - 1]; 
            } 
             
            // if the number is odd 
            else
            { 
                countEVEN[i] = countEVEN[i - 1] + 
                               countODD[i - 1]; 
     
                countODD[i] = countODD[i - 1] + 
                              countEVEN[i - 1] + 1; 
            } 
        }
         
        int[] ans = new int[2];
        ans[0] = countEVEN[n];
        ans[1] = countODD[n];
        return ans;
    } 
 
    // Driver Code
    public static void main (String[] args) 
    {
        int[] arr = new int[]{ 1, 2, 2, 3 }; 
        int n = 4;
        int[] ans = countSum(arr, n);
        System.out.println("EvenSum = " + ans[0]);
        System.out.println("OddSum = " + ans[1]);
    }
}
 
// This code is contributed by Shivam Sharma 

Python3

# Python3 implementation of above approach
 
# Returns the count of odd and
# even subsequences
def countSum(arr, n):
     
    result = 0
 
    # Variables to store the count of even
    # subsequences and odd subsequences
 
    # Initialising count_even and count_odd to 0
    # since as there is no subsequence before the
    # iteration with even or odd count.
    count_odd = 0
    count_even = 0
 
    # Find sum of all subsequences with even count
    # and odd count and storing them as we iterate.
 
    for i in range(n):
 
        # if the number is even
        if arr[i - 1] % 2 == 0:
            count_even = count_even + count_even + 1
            count_odd = count_odd + count_odd
 
        # if the number is odd
        else:
            temp = count_even
            count_even = count_even + count_odd
            count_odd = count_odd + temp + 1
         
    return [count_even, count_odd]
 
# Driver code
arr = [ 1, 2, 2, 3 ]
n = len(arr)
 
# Calling the function
ans = countSum(arr, n)
 
print('EvenSum =', ans[0], 
      'OddSum =', ans[1])
 
# This code is contributed 
# by Saurabh_shukla

C#

// C# implementation to find the number 
// of Subsequences with Even and Odd Sum 
using System;
class GFG 
{
    public static int[] countSum(int []arr, int n)
    {
 
        // Arrays to store the count of even 
        // subsequences and odd subsequences 
        int[] countODD = new int[n + 1];
        int[] countEVEN = new int[n + 1];
         
        // Initialising countEVEN[0] and countODD[0] to 0 
        // since as there is no subsequence before the 
        // iteration with even or odd count. 
        countODD[0] = 0; 
        countEVEN[0] = 0; 
         
        // Find sum of all subsequences with even count 
        // and odd count storing them as we iterate. 
     
        // Here countEVEN[i] denotes count of 
        // even subsequences till i 
     
        // Here countODD[i] denotes count of 
        // odd subsequences till i 
        for (int i = 1; i <= n; i++) 
        { 
 
            // if the number is even 
            if (arr[i - 1] % 2 == 0)
            { 
                countEVEN[i] = countEVEN[i - 1] + 
                               countEVEN[i - 1] + 1; 
     
                countODD[i] = countODD[i - 1] + 
                              countODD[i - 1]; 
            } 
             
            // if the number is odd 
            else
            { 
                countEVEN[i] = countEVEN[i - 1] + 
                               countODD[i - 1]; 
     
                countODD[i] = countODD[i - 1] + 
                              countEVEN[i - 1] + 1; 
            } 
        }
         
        int[] ans = new int[2];
        ans[0] = countEVEN[n];
        ans[1] = countODD[n];
        return ans;
    } 
 
    // Driver Code
    public static void Main (String[] args) 
    {
        int[] arr = new int[]{ 1, 2, 2, 3 }; 
        int n = 4;
        int[] ans = countSum(arr, n);
        Console.WriteLine("EvenSum = " + ans[0]);
        Console.WriteLine("OddSum = " + ans[1]);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
  
// JavaScript implementation to find the number 
// of Subsequences with Even and Odd Sum 
function countSum(arr, n)
{
    // Arrays to store the count of even 
    // subsequences and odd subsequences 
    var countODD = Array(n+1).fill(0);
    var countEVEN = Array(n+1).fill(0);
     
    // Initialising countEVEN[0] and countODD[0] to 0 
    // since as there is no subsequence before the 
    // iteration with even or odd count. 
    countODD[0] = 0; 
    countEVEN[0] = 0; 
     
    // Find sum of all subsequences with even count 
    // and odd count storing them as we iterate. 
 
    // Here countEVEN[i] denotes count of 
    // even subsequences till i 
 
    // Here countODD[i] denotes count of 
    // odd subsequences till i 
    for (var i = 1; i <= n; i++) 
    { 
        // if the number is even 
        if (arr[i - 1] % 2 == 0)
        { 
            countEVEN[i] = countEVEN[i - 1] + 
                           countEVEN[i - 1] + 1; 
 
            countODD[i] = countODD[i - 1] + 
                          countODD[i - 1]; 
        } 
         
        // if the number is odd 
        else
        { 
            countEVEN[i] = countEVEN[i - 1] + 
                           countODD[i - 1]; 
 
            countODD[i] = countODD[i - 1] + 
                          countEVEN[i - 1] + 1; 
        } 
    }
     
    var ans = [0,0];
    ans[0] = countEVEN[n];
    ans[1] = countODD[n];
    return ans;
} 
// Driver Code
var arr = [ 1, 2, 2, 3 ]; 
var n = 4;
var ans = countSum(arr, n);
document.write("EvenSum = " + ans[0]);
document.write(" OddSum = " + ans[1]);
 
 
</script>

Output:

EvenSum = 7 OddSum = 8

Time Complexity: O(N).
Space Complexity: O(N) where N is the number of elements in the array.

Efficient Approach:
Instead of making countEVEN[N] and countODD[N] arrays we only need the count_even variable and count_odd variable and changing it the same way as we did earlier.
Below is the implementation of above approach:

C++

// C++ implementation
#include <bits/stdc++.h>
using namespace std;
 
// Returns the count of odd and
// even subsequences
pair<int, int> countSum(int arr[], int n)
{
    int result = 0;
 
    // Variables to store the count of even
    // subsequences and odd subsequences
    int count_odd, count_even;
 
    // Initialising count_even and count_odd to 0
    // since as there is no subsequence before the
    // iteration with even or odd count.
    count_odd = 0;
    count_even = 0;
 
    // Find sum of all subsequences with even count
    // and odd count and storing them as we iterate.
 
    for (int i = 1; i <= n; i++) {
 
        // if the number is even
        if (arr[i - 1] % 2 == 0) {
            count_even = count_even + count_even + 1;
            count_odd = count_odd + count_odd;
        }
 
        // if the number is odd
        else {
            int temp = count_even;
            count_even = count_even + count_odd;
            count_odd = count_odd + temp + 1;
        }
    }
 
    return { count_even, count_odd };
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Calling the function
 
    pair<int, int> ans = countSum(arr, n);
 
    cout << "EvenSum = " << ans.first;
    cout << " OddSum = " << ans.second;
 
    return 0;
}

Java

// Java program to get minimum cost to sort
// strings by reversal operation
class GFG
{
 
static class pair
{ 
    int first, second; 
    public pair(int first, int second) 
    { 
        this.first = first; 
        this.second = second; 
    } 
} 
 
// Returns the count of odd and
// even subsequences
static pair countSum(int arr[], int n)
{
    int result = 0;
 
    // Variables to store the count of even
    // subsequences and odd subsequences
    int count_odd, count_even;
 
    // Initialising count_even and count_odd to 0
    // since as there is no subsequence before the
    // iteration with even or odd count.
    count_odd = 0;
    count_even = 0;
 
    // Find sum of all subsequences with even count
    // and odd count and storing them as we iterate.
    for (int i = 1; i <= n; i++)
    {
 
        // if the number is even
        if (arr[i - 1] % 2 == 0)
        {
            count_even = count_even + count_even + 1;
            count_odd = count_odd + count_odd;
        }
 
        // if the number is odd
        else
        {
            int temp = count_even;
            count_even = count_even + count_odd;
            count_odd = count_odd + temp + 1;
        }
    }
    return new pair(count_even, count_odd );
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 2, 3 };
    int n = arr.length;
 
    // Calling the function
 
    pair ans = countSum(arr, n);
 
    System.out.print("EvenSum = " + ans.first);
    System.out.print(" OddSum = " + ans.second);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of above approach
 
# Returns the count of odd and 
# even subsequences 
def countSum(arr, n):
    result = 0
     
    # Variables to store the count of even 
    # subsequences and odd subsequences 
    # Initialising count_even and count_odd to 0 
    # since as there is no subsequence before the 
    # iteration with even or odd count. 
    count_odd = 0
    count_even = 0
 
    # Find sum of all subsequences with even count 
    # and odd count and storing them as we iterate. 
 
    for i in range(1, n + 1):
         
        # if the number is even 
        if (arr[i - 1] % 2 == 0):
            count_even = count_even + count_even + 1
            count_odd = count_odd + count_odd
 
        # if the number is odd 
        else:
            temp = count_even
            count_even = count_even + count_odd
            count_odd = count_odd + temp + 1
 
    return (count_even, count_odd) 
     
# Driver code 
arr = [1, 2, 2, 3]; 
n = len(arr)
 
# Calling the function 
count_even, count_odd = countSum(arr, n); 
 
print("EvenSum = ", count_even, 
      " OddSum = ", count_odd)
       
# This code is contributed 
# by ANKITKUMAR34

C#

// C# program to get minimum cost to sort
// strings by reversal operation
using System;
     
class GFG
{
 
public class pair
{ 
    public int first, second; 
    public pair(int first, int second) 
    { 
        this.first = first; 
        this.second = second; 
    } 
} 
 
// Returns the count of odd and
// even subsequences
static pair countSum(int []arr, int n)
{
    // Variables to store the count of even
    // subsequences and odd subsequences
    int count_odd, count_even;
 
    // Initialising count_even and count_odd to 0
    // since as there is no subsequence before the
    // iteration with even or odd count.
    count_odd = 0;
    count_even = 0;
 
    // Find sum of all subsequences with even count
    // and odd count and storing them as we iterate.
    for (int i = 1; i <= n; i++)
    {
 
        // if the number is even
        if (arr[i - 1] % 2 == 0)
        {
            count_even = count_even + count_even + 1;
            count_odd = count_odd + count_odd;
        }
 
        // if the number is odd
        else
        {
            int temp = count_even;
            count_even = count_even + count_odd;
            count_odd = count_odd + temp + 1;
        }
    }
    return new pair(count_even, count_odd );
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 2, 3 };
    int n = arr.Length;
 
    // Calling the function
 
    pair ans = countSum(arr, n);
 
    Console.Write("EvenSum = " + ans.first);
    Console.Write(" OddSum = " + ans.second);
}
} 
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Java program to get minimum cost to sort
// strings by reversal operation
var first, second; 
function pair( first,  second) 
{ 
    this.first = first; 
    this.second = second; 
} 
 
// Returns the count of odd and
// even subsequences
function countSum(arr, n)
{
    var result = 0;
 
    // Variables to store the count of even
    // subsequences and odd subsequences
    var count_odd, count_even;
 
    // Initialising count_even and count_odd to 0
    // since as there is no subsequence before the
    // iteration with even or odd count.
    count_odd = 0;
    count_even = 0;
 
    // Find sum of all subsequences with even count
    // and odd count and storing them as we iterate.
    for (var i = 1; i <= n; i++)
    {
 
        // if the number is even
        if (arr[i - 1] % 2 == 0)
        {
            count_even = count_even + count_even + 1;
            count_odd = count_odd + count_odd;
        }
 
        // if the number is odd
        else
        {
            var temp = count_even;
            count_even = count_even + count_odd;
            count_odd = count_odd + temp + 1;
        }
    }
    return new pair(count_even, count_odd );
}
 
// Driver code
var arr = [ 1, 2, 2, 3 ];
var n = arr.length;
 
// Calling the function
 
var ans = countSum(arr, n);
 
document.write("EvenSum = " + ans.first);
document.write(" OddSum = " + ans.second);
 
// This code is contributed by shivanisinghss2110
 
</script>

Output:

EvenSum = 7 OddSum = 8

Time Complexity: O(N).
Space Complexity: O(1), where N is the number of elements in the array.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!