Count number of ways to get Odd Sum
Given N pairs of numbers. The task is to count ways to choose exactly one number from each pair such that the sum of those numbers is odd.
Examples:
Input:
N = 2
3 4
1 2
Output: 2
Explanation:
We can choose 3 from the first pair and 2 from the second pair, and their sum is 5 which is odd.
Also, we can choose 4 from the first pair and 1 from the second pair, and their sum is 5 which is odd.
So the total possible ways will be 2.
Input:
N = 2
2 2
2 2
Output: 0
Approach 1: Recursive Approach:
This approach uses recursion to solve the problem. It recursively processes each pair of elements in the array and calculates the count of ways to get an odd sum by choosing one element from each pair. It returns the count of ways to get an odd sum for the entire array.
Here is the code of this approach:
C++
#include <iostream> using namespace std; int CountOfOddSumHelper( int a[][2], int n, int pair, int sum); int CountOfOddSum( int a[][2], int n) { // Call the recursive function with initial values return CountOfOddSumHelper(a, n, 0, 0); } int CountOfOddSumHelper( int a[][2], int n, int pair, int sum) { // Base case: If we have processed all the pairs, // check if the sum is odd and return 1 or 0 accordingly if (pair == n) { return sum % 2 == 1 ? 1 : 0; } // Recursively process the current pair for both // odd and even elements int cnt1 = CountOfOddSumHelper(a, n, pair + 1, sum + a[pair][0]); int cnt2 = CountOfOddSumHelper(a, n, pair + 1, sum + a[pair][1]); // Return the sum of counts for odd elements in the current pair return cnt1 + cnt2; } // Driver code int main() { int a[][2] = { { 1, 2 }, { 3, 6 } }; int n = sizeof (a) / sizeof (a[0]); int ans = CountOfOddSum(a, n); cout << ans << endl; return 0; } |
Java
public class Main { public static int CountOfOddSumHelper( int [][] a, int n, int pair, int sum) { // Base case: If we have processed all the pairs, // check if the sum is odd and return 1 or 0 accordingly if (pair == n) { return sum % 2 == 1 ? 1 : 0 ; } // Recursively process the current pair for both // odd and even elements int cnt1 = CountOfOddSumHelper(a, n, pair + 1 , sum + a[pair][ 0 ]); int cnt2 = CountOfOddSumHelper(a, n, pair + 1 , sum + a[pair][ 1 ]); // Return the sum of counts for odd elements in the current pair return cnt1 + cnt2; } public static int CountOfOddSum( int [][] a, int n) { // Call the recursive function with initial values return CountOfOddSumHelper(a, n, 0 , 0 ); } public static void main(String[] args) { int [][] a = { { 1 , 2 }, { 3 , 6 } }; int n = a.length; int ans = CountOfOddSum(a, n); System.out.println(ans); } } |
Python3
def count_of_odd_sum_helper(a, n, pair, sum ): # Base case: If we have processed all the pairs, # check if the sum is odd and return 1 or 0 accordingly if pair = = n: return 1 if sum % 2 = = 1 else 0 # Recursively process the current pair for both # odd and even elements cnt1 = count_of_odd_sum_helper(a, n, pair + 1 , sum + a[pair][ 0 ]) cnt2 = count_of_odd_sum_helper(a, n, pair + 1 , sum + a[pair][ 1 ]) # Return the sum of counts for odd elements in the current pair return cnt1 + cnt2 def count_of_odd_sum(a): # Call the recursive function with initial values return count_of_odd_sum_helper(a, len (a), 0 , 0 ) # Driver code a = [[ 1 , 2 ], [ 3 , 6 ]] ans = count_of_odd_sum(a) print (ans) |
Javascript
function countOfOddSumHelper(a, n, pair, sum) { // Base case: If we have processed all the pairs, // check if the sum is odd and return 1 or 0 accordingly if (pair === n) { return sum % 2 === 1 ? 1 : 0; } // Recursively process the current pair for both // odd and even elements let cnt1 = countOfOddSumHelper(a, n, pair + 1, sum + a[pair][0]); let cnt2 = countOfOddSumHelper(a, n, pair + 1, sum + a[pair][1]); // Return the sum of counts for odd elements in the current pair return cnt1 + cnt2; } function countOfOddSum(a, n) { // Call the recursive function with initial values return countOfOddSumHelper(a, n, 0, 0); } // Driver code const a = [[1, 2], [3, 6]]; const n = a.length; const ans = countOfOddSum(a, n); console.log(ans); |
C#
using System; class GFG { static int CountOfOddSum( int [,] a, int n) { // Call the recursive function with initial values return CountOfOddSumHelper(a, n, 0, 0); } static int CountOfOddSumHelper( int [,] a, int n, int pair, int sum) { // Base case: If we have processed all the pairs, // check if the sum is odd and return 1 or 0 accordingly if (pair == n) { return sum % 2 == 1 ? 1 : 0; } // Recursively process the current pair for both // odd and even elements int cnt1 = CountOfOddSumHelper(a, n, pair + 1, sum + a[pair, 0]); int cnt2 = CountOfOddSumHelper(a, n, pair + 1, sum + a[pair, 1]); // Return the sum of counts for odd elements in the current pair return cnt1 + cnt2; } // Driver code public static void Main() { int [,] a = { { 1, 2 }, { 3, 6 } }; int n = a.GetLength(0); int ans = CountOfOddSum(a, n); Console.WriteLine(ans); } } |
OUTPUT:
2
Time Complexity: O(N^2)
Auxiliary Space :O(N), where N is the size of the given 2-d array.
Approach 2: DP Approach:
- We will use dynamic programming here, where dp[i][0] will store a number of possible ways to get an even sum upto i’th pair and dp[i][1] will store number of possible ways to get odd sum upto i’th pair.
- cnt[i][0] will store count of even numbers in i’th pair and cnt[i][1] will store count of odd numbers in i’th pair.
- It is known that the sum of two even or sum of two odd will always be even and the sum of one even and one odd will always be odd.
- We apply this to store the count in the DP array.
- Ways to get even sum upto i’th pair will be dp[i – 1][0] * cnt[i][0] + dp[i – 1][1] * cnt[i][1].
- Ways to get odd sum upto i’th pair will be dp[i – 1][1] * cnt[i][0] + dp[i – 1][0] * cnt[i][1].
Below is the implementation of above Approach:
C++
// C++ implementation #include <bits/stdc++.h> using namespace std; // Count the ways to sum up with odd // by choosing one element form each // pair int CountOfOddSum( int a[][2], int n) { int dp[n][2], cnt[n][2]; // Initialize two array with 0 memset (dp, 0, sizeof (dp)); memset (cnt, 0, sizeof (cnt)); for ( int i = 0; i < n; i++) { for ( int j = 0; j < 2; j++) { // if element is even if (a[i][j] % 2 == 0) { // store count of even // number in i'th pair cnt[i][0]++; } // if the element is odd else { // store count of odd // number in i'th pair cnt[i][1]++; } } } // Initial state of dp array dp[0][0] = cnt[0][0], dp[0][1] = cnt[0][1]; for ( int i = 1; i < n; i++) { // dp[i][0] = total number of ways // to get even sum upto i'th pair dp[i][0] = (dp[i - 1][0] * cnt[i][0] + dp[i - 1][1] * cnt[i][1]); // dp[i][1] = total number of ways // to odd even sum upto i'th pair dp[i][1] = (dp[i - 1][0] * cnt[i][1] + dp[i - 1][1] * cnt[i][0]); } // dp[n - 1][1] = total number of ways // to get odd sum upto n'th pair return dp[n - 1][1]; } // Driver code int main() { int a[][2] = { { 1, 2 }, { 3, 6 } }; int n = sizeof (a) / sizeof (a[0]); int ans = CountOfOddSum(a, n); cout << ans << "\n" ; return 0; } |
Java
// Java implementation of above approach class GFG { // Count the ways to sum up with odd // by choosing one element form each // pair static int CountOfOddSum( int a[][], int n) { int [][]dp = new int [n][ 2 ]; int [][]cnt = new int [n][ 2 ]; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < 2 ; j++) { // if element is even if (a[i][j] % 2 == 0 ) { // store count of even // number in i'th pair cnt[i][ 0 ]++; } // if the element is odd else { // store count of odd // number in i'th pair cnt[i][ 1 ]++; } } } // Initial state of dp array dp[ 0 ][ 0 ] = cnt[ 0 ][ 0 ]; dp[ 0 ][ 1 ] = cnt[ 0 ][ 1 ]; for ( int i = 1 ; i < n; i++) { // dp[i][0] = total number of ways // to get even sum upto i'th pair dp[i][ 0 ] = (dp[i - 1 ][ 0 ] * cnt[i][ 0 ] + dp[i - 1 ][ 1 ] * cnt[i][ 1 ]); // dp[i][1] = total number of ways // to odd even sum upto i'th pair dp[i][ 1 ] = (dp[i - 1 ][ 0 ] * cnt[i][ 1 ] + dp[i - 1 ][ 1 ] * cnt[i][ 0 ]); } // dp[n - 1][1] = total number of ways // to get odd sum upto n'th pair return dp[n - 1 ][ 1 ]; } // Driver code public static void main (String[] args) { int a[][] = {{ 1 , 2 }, { 3 , 6 }}; int n = a.length; int ans = CountOfOddSum(a, n); System.out.println(ans); } } // This code is contributed by ihritik |
Python3
# Python3 implementation of the above approach # Count the ways to sum up with odd # by choosing one element form each # pair def CountOfOddSum(a, n): dp = [[ 0 for i in range ( 2 )] for i in range (n)] cnt = [[ 0 for i in range ( 2 )] for i in range (n)] # Initialize two array with 0 for i in range (n): for j in range ( 2 ): # if element is even if (a[i][j] % 2 = = 0 ): #store count of even #number in i'th pair cnt[i][ 0 ] + = 1 # if the element is odd else : # store count of odd # number in i'th pair cnt[i][ 1 ] + = 1 # Initial state of dp array dp[ 0 ][ 0 ] = cnt[ 0 ][ 0 ] dp[ 0 ][ 1 ] = cnt[ 0 ][ 1 ] for i in range ( 1 , n): # dp[i][0] = total number of ways # to get even sum upto i'th pair dp[i][ 0 ] = (dp[i - 1 ][ 0 ] * cnt[i][ 0 ] + dp[i - 1 ][ 1 ] * cnt[i][ 1 ]) # dp[i][1] = total number of ways # to odd even sum upto i'th pair dp[i][ 1 ] = (dp[i - 1 ][ 0 ] * cnt[i][ 1 ] + dp[i - 1 ][ 1 ] * cnt[i][ 0 ]) # dp[n - 1][1] = total number of ways # to get odd sum upto n'th pair return dp[n - 1 ][ 1 ] # Driver code a = [[ 1 , 2 ] , [ 3 , 6 ] ] n = len (a) ans = CountOfOddSum(a, n) print (ans) # This code is contributed by Mohit Kumar |
C#
// C# implementation of above approach using System; class GFG { // Count the ways to sum up with odd // by choosing one element form each // pair static int CountOfOddSum( int [ , ] a, int n) { int [ , ]dp = new int [n, 2]; int [ , ]cnt = new int [n, 2]; for ( int i = 0; i < n; i++) { for ( int j = 0; j < 2; j++) { // if element is even if (a[i, j] % 2 == 0) { // store count of even // number in i'th pair cnt[i, 0]++; } // if the element is odd else { // store count of odd // number in i'th pair cnt[i, 1]++; } } } // Initial state of dp array dp[0, 0] = cnt[0, 0]; dp[0, 1] = cnt[0, 1]; for ( int i = 1; i < n; i++) { // dp[i, 0] = total number of ways // to get even sum upto i'th pair dp[i, 0] = (dp[i - 1, 0] * cnt[i, 0] + dp[i - 1, 1] * cnt[i, 1]); // dp[i, 1] = total number of ways // to odd even sum upto i'th pair dp[i, 1] = (dp[i - 1, 0] * cnt[i, 1] + dp[i - 1, 1] * cnt[i, 0]); } // dp[n - 1, 1] = total number of ways // to get odd sum upto n'th pair return dp[n - 1, 1]; } // Driver code public static void Main () { int [ , ] a = { { 1, 2 }, { 3, 6 } }; int n = a.GetLength(1); int ans = CountOfOddSum(a, n); Console.WriteLine(ans); } } // This code is contributed by ihritik |
Javascript
<script> // Javascript implementation // Count the ways to sum up with odd // by choosing one element form each // pair function CountOfOddSum(a, n) { let dp = new Array(n), cnt = new Array(n); for (let i = 0; i < n; i++) { dp[i] = new Array(2).fill(0); cnt[i] = new Array(2).fill(0); } for (let i = 0; i < n; i++) { for (let j = 0; j < 2; j++) { // if element is even if (a[i][j] % 2 == 0) { // store count of even // number in i'th pair cnt[i][0]++; } // if the element is odd else { // store count of odd // number in i'th pair cnt[i][1]++; } } } // Initial state of dp array dp[0][0] = cnt[0][0], dp[0][1] = cnt[0][1]; for (let i = 1; i < n; i++) { // dp[i][0] = total number of ways // to get even sum upto i'th pair dp[i][0] = (dp[i - 1][0] * cnt[i][0] + dp[i - 1][1] * cnt[i][1]); // dp[i][1] = total number of ways // to odd even sum upto i'th pair dp[i][1] = (dp[i - 1][0] * cnt[i][1] + dp[i - 1][1] * cnt[i][0]); } // dp[n - 1][1] = total number of ways // to get odd sum upto n'th pair return dp[n - 1][1]; } // Driver code let a = [ [ 1, 2 ], [ 3, 6 ] ]; let n = a.length; let ans = CountOfOddSum(a, n); document.write(ans); </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(2 * N) ? O(N), where N is the size of the given 2-d array.
Contact Us