Given an array arr[] of integers, the task is to check if it is possible to obtain a subsequence of K elements from the array such that their sum is odd. If it is possible, print Yes. Otherwise, print No.
Examples:
Input: arr[] = { 2, 5, 6, 7, 4 }, K = 3
Output: Yes
Explanation:
Subsequences {2, 5, 6}, {2, 6, 7} and {2, 7, 4} have odd sum
Input: arr[] = { 1, 5, 7, 11 }, K = 4
Output: No
Explanation:
Only subsequence of length 4 is {1, 5, 7, 11} which has even sum (24). Hence no such subsequence exists.
Naive Approach:
The simplest method to solve the problem is to generate all subsequences of length K and check if any of these subsequences have an odd sum. The time complexity for such an approach will be exponential and thus inefficient.
Efficient Approach:
The efficient method to approach the above problem will be to count the number of odd elements in the array and then, simply checking for all the edge cases when it will not be possible to find a subsequence with odd sum.
The edge cases to be considered when such a subsequence cannot be generated are as follows:
- If there are no odd elements in the array, any subsequence will contain only even elements and an even sum will be obtained. So, it is not possible to generate a subsequence with odd sum.
- If K is even and there are no even elements present in the array, a subsequence with odd sum is not possible.
For all other cases, it will be possible to generate a subsequence with an odd sum.
Below is the implementation of above approach:
C++
// C++ program to check if a// subsequence of length K// with odd sum exists in the// given array#include <bits/stdc++.h>using namespace std;// Function to check if any required// subsequence exists or notbool isSubseqPossible(int arr[], int N, int K){ int i; // Store count of odd and // even elements in the array int odd = 0, even = 0; // Calculate the count of // odd and even elements for (i = 0; i < N; i++) { if (arr[i] % 2 == 1) odd++; else even++; } // If no odd elements exists // or no even elements exists // when K is even if (odd == 0 || (even == 0 && K % 2 == 0)) // Subsequence is not possible return false; // Possible otherwise return true;}// Driver Codeint main(){ int arr[] = { 2, 3, 5, 7, 4 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; cout << (isSubseqPossible(arr, N, K) ? "Yes" : "No"); return 0;} |
Java
// Java program to check if a// subsequence of length K// with odd sum exists in the// given arrayclass GFG{// Function to check if any required// subsequence exists or notstatic boolean isSubseqPossible(int []arr, int N, int K){ int i; // Store count of odd and // even elements in the array int odd = 0, even = 0; // Calculate the count of // odd and even elements for (i = 0; i < N; i++) { if (arr[i] % 2 == 1) odd++; else even++; } // If no odd elements exists // or no even elements exists // when K is even if (odd == 0 || (even == 0 && K % 2 == 0)) // Subsequence is not possible return false; // Possible otherwise return true;}// Driver Codepublic static void main(String args[]){ int []arr = { 2, 3, 5, 7, 4 }; int N = arr.length; int K = 3; System.out.print(isSubseqPossible(arr, N, K) ? "Yes" : "No");}}// This code is contributed by Code_Mech |
Python3
# Python3 program to check if a subsequence# of length K with odd sum exists in the# given array# Function to check if any required# subsequence exists or notdef isSubseqPossible(arr, N, K): i = 0 # Store count of odd and # even elements in the array odd = 0 even = 0 # Calculate the count of # odd and even elements for i in range(N): if (arr[i] % 2 == 1): odd += 1 else: even += 1 # If no odd element exists or no # even element exists when K even if (odd == 0 or (even == 0 and K % 2 == 0)): # Subsequence is not possible return False # Otherwise possible return True# Driver codeif __name__ == '__main__': arr = [ 2, 3, 5, 7, 4 ] N = len(arr) K = 3 print("Yes" if isSubseqPossible(arr, N, K) else "No")# This code is contributed by himanshu77 |
C#
// C# program to check if a// subsequence of length K// with odd sum exists in the// given arrayusing System;class GFG{// Function to check if any required// subsequence exists or notstatic bool isSubseqPossible(int []arr, int N, int K){ int i; // Store count of odd and // even elements in the array int odd = 0, even = 0; // Calculate the count of // odd and even elements for (i = 0; i < N; i++) { if (arr[i] % 2 == 1) odd++; else even++; } // If no odd elements exists // or no even elements exists // when K is even if (odd == 0 || (even == 0 && K % 2 == 0)) // Subsequence is not possible return false; // Possible otherwise return true;}// Driver Codepublic static void Main(){ int []arr = { 2, 3, 5, 7, 4 }; int N = arr.Length; int K = 3; Console.Write(isSubseqPossible(arr, N, K) ? "Yes" : "No");}}// This code is contributed by Code_Mech |
Javascript
<script>// JavaScript program to check if a// subsequence of length K// with odd sum exists in the// given array// Function to check if any required// subsequence exists or notfunction isSubseqPossible(arr, N, K){ let i; // Store count of odd and // even elements in the array let odd = 0, even = 0; // Calculate the count of // odd and even elements for (i = 0; i < N; i++) { if (arr[i] % 2 == 1) odd++; else even++; } // If no odd elements exists // or no even elements exists // when K is even if (odd == 0 || (even == 0 && K % 2 == 0)) // Subsequence is not possible return false; // Possible otherwise return true;} // Driver Code let arr = [ 2, 3, 5, 7, 4 ]; let N = arr.length; let K = 3; document.write(isSubseqPossible(arr, N, K) ? "Yes" : "No"); </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach#2: Using itertools combinations()
The approach used in this code is to generate all possible subsequences of length K using the itertools.combinations() function and check if any subsequence has an odd sum.
Algorithm
1. Use the itertools.combinations() function to generate all possible subsequences of length K from the input array.
2. Loop through each subsequence and check if its sum is odd using the sum() function and the modulo operator.
3. If a subsequence with an odd sum is found, return “Yes”.
4. If no subsequence with an odd sum is found, return “No”.
C++
#include <iostream>#include <vector>using namespace std;string subsequenceWithOddSum(vector<int>& arr, int K) { int n = arr.size(); for (int mask = 0; mask < (1 << n); mask++) { int sum = 0; // Initialize the sum for the current subsequence int count = 0; // Initialize the count for the current subsequence for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) { // If the i-th element is included in the current subsequence // (according to the mask) sum += arr[i]; // Add the element to the sum count++; // Increment the count of elements in the current subsequence } } if (count == K && sum % 2 == 1) { // If the length of the current subsequence is K and the sum is odd return "Yes"; // Return "Yes" } } return "No"; // If no such subsequence is found, return "No"}int main() { vector<int> arr = {1, 5, 7, 11}; int K = 4; cout << subsequenceWithOddSum(arr, K) << endl; return 0;} |
Java
import java.util.*;public class SubsequenceWithOddSum { public static String subsequenceWithOddSum(int[] arr, int K) { int n = arr.length; for (int mask = 0; mask < (1 << n); mask++) { int sum = 0; // Initialize the sum for the current subsequence int count = 0; // Initialize the count for the current subsequence for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) { // If the i-th element is included in the current subsequence (according to the mask) sum += arr[i]; // Add the element to the sum count++; // Increment the count of elements in the current subsequence } } if (count == K && sum % 2 == 1) { // If the length of the current subsequence is K and the sum is odd return "Yes"; // Return "Yes" } } return "No"; // If no such subsequence is found, return "No" } public static void main(String[] args) { int[] arr = {1, 5, 7, 11}; int K = 4; System.out.println(subsequenceWithOddSum(arr, K)); }} |
Python3
import itertoolsdef subsequence_with_odd_sum(arr, K): for sub in itertools.combinations(arr, K): if sum(sub) % 2 == 1: return "Yes" return "No"# Example usagearr = [1, 5, 7, 11]K = 4print(subsequence_with_odd_sum(arr, K))# Output: Yes |
No
Time Complexity: O(n^K), where n is the length of the input array. This is because the algorithm generates all possible subsequences of length K, which can be as many as n^K.
Space Complexity: O(K), which is the maximum size of the subsequence stored at any given time. This is because the algorithm only stores one subsequence at a time while checking its sum.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
