Given an array arr[] of n integers and an integer K, the task is to find the number of ways to select exactly K even numbers from the given array.
Examples:
Input: arr[] = {1, 2, 3, 4} k = 1
Output: 2
Explanation:
The number of ways in which we can select one even number is 2.Input: arr[] = {61, 65, 99, 26, 57, 68, 23, 2, 32, 30} k = 2
Output:10
Explanation:
The number of ways in which we can select 2 even number is 10.
Approach: The idea is to apply the rule of combinatorics. For choosing r objects from the given n objects, the total number of ways of choosing is given by nCr. Below are the steps:
- Count the total number of even elements from the given array(say cnt).
- Check if the value of K is greater than cnt then the number of ways will be equal to 0.
- Otherwise, the answer will be nCk.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; long long f[12]; // Function for calculating factorial void fact() { // Factorial of n defined as: // n! = n * (n - 1) * ... * 1 f[0] = f[1] = 1; for ( int i = 2; i <= 10; i++) f[i] = i * 1LL * f[i - 1]; } // Function to find the number of ways to // select exactly K even numbers // from the given array void solve( int arr[], int n, int k) { fact(); // Count even numbers int even = 0; for ( int i = 0; i < n; i++) { // Check if the current // number is even if (arr[i] % 2 == 0) even++; } // Check if the even numbers to be // chosen is greater than n. Then, // there is no way to pick it. if (k > even) cout << 0 << endl; else { // The number of ways will be nCk cout << f[even] / (f[k] * f[even - k]); } } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 3, 4 }; int n = sizeof arr / sizeof arr[0]; // Given count of even elements int k = 1; // Function Call solve(arr, n, k); return 0; } |
Java
// Java program for the above approach class GFG{ static int []f = new int [ 12 ]; // Function for calculating factorial static void fact() { // Factorial of n defined as: // n! = n * (n - 1) * ... * 1 f[ 0 ] = f[ 1 ] = 1 ; for ( int i = 2 ; i <= 10 ; i++) f[i] = i * 1 * f[i - 1 ]; } // Function to find the number of ways to // select exactly K even numbers // from the given array static void solve( int arr[], int n, int k) { fact(); // Count even numbers int even = 0 ; for ( int i = 0 ; i < n; i++) { // Check if the current // number is even if (arr[i] % 2 == 0 ) even++; } // Check if the even numbers to be // chosen is greater than n. Then, // there is no way to pick it. if (k > even) System.out.print( 0 + "\n" ); else { // The number of ways will be nCk System.out.print(f[even] / (f[k] * f[even - k])); } } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 1 , 2 , 3 , 4 }; int n = arr.length; // Given count of even elements int k = 1 ; // Function call solve(arr, n, k); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach f = [ 0 ] * 12 # Function for calculating factorial def fact(): # Factorial of n defined as: # n! = n * (n - 1) * ... * 1 f[ 0 ] = f[ 1 ] = 1 for i in range ( 2 , 11 ): f[i] = i * 1 * f[i - 1 ] # Function to find the number of ways to # select exactly K even numbers # from the given array def solve(arr, n, k): fact() # Count even numbers even = 0 for i in range (n): # Check if the current # number is even if (arr[i] % 2 = = 0 ): even + = 1 # Check if the even numbers to be # chosen is greater than n. Then, # there is no way to pick it. if (k > even): print ( 0 ) else : # The number of ways will be nCk print (f[even] / / (f[k] * f[even - k])) # Driver Code # Given array arr[] arr = [ 1 , 2 , 3 , 4 ] n = len (arr) # Given count of even elements k = 1 # Function call solve(arr, n, k) # This code is contributed by code_hunt |
C#
// C# program for the above approach using System; class GFG{ static int []f = new int [12]; // Function for calculating factorial static void fact() { // Factorial of n defined as: // n! = n * (n - 1) * ... * 1 f[0] = f[1] = 1; for ( int i = 2; i <= 10; i++) f[i] = i * 1 * f[i - 1]; } // Function to find the number of ways to // select exactly K even numbers // from the given array static void solve( int []arr, int n, int k) { fact(); // Count even numbers int even = 0; for ( int i = 0; i < n; i++) { // Check if the current // number is even if (arr[i] % 2 == 0) even++; } // Check if the even numbers to be // chosen is greater than n. Then, // there is no way to pick it. if (k > even) Console.Write(0 + "\n" ); else { // The number of ways will be nCk Console.Write(f[even] / (f[k] * f[even - k])); } } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = { 1, 2, 3, 4 }; int n = arr.Length; // Given count of even elements int k = 1; // Function call solve(arr, n, k); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript program for the above approach var f = Array(12).fill(0); // Function for calculating factorial function fact() { // Factorial of n defined as: // n! = n * (n - 1) * ... * 1 f[0] = f[1] = 1; for ( var i = 2; i <= 10; i++) f[i] = i * 1 * f[i - 1]; } // Function to find the number of ways to // select exactly K even numbers // from the given array function solve(arr, n, k) { fact(); // Count even numbers var even = 0; for ( var i = 0; i < n; i++) { // Check if the current // number is even if (arr[i] % 2 == 0) even++; } // Check if the even numbers to be // chosen is greater than n. Then, // there is no way to pick it. if (k > even) document.write( 0 ); else { // The number of ways will be nCk document.write( f[even] / (f[k] * f[even - k])); } } // Driver Code // Given array arr[] var arr = [ 1, 2, 3, 4 ]; var n = arr.length; // Given count of even elements var k = 1; // Function Call solve(arr, n, k); </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : Space optimization
we can optimize the space complexity of previous program by avoiding the use of an array to store factorials. We can compute the factorials on the go and use them directly in the calculation. This will reduce the space complexity from O(n) to O(1)
Implementation steps:
- Initialize a variable even to count the number of even numbers in the array.
- Loop through the array and increment even if the current number is even.
- Check if the number of even numbers to be chosen (k) is greater than the total number of even numbers in the array. If so, there is no way to pick k even numbers, so print 0 and return.
- Else compute the factorials on the go using two variables numerator and denominator.
- Loop from even down to even – k + 1, and multiply numerator by each number.
- Loop from 1 to k, and multiply denominator by each number.
- Compute and print the combination using numerator / denominator.
Implementation:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of ways to // select exactly K even numbers // from the given array void solve( int arr[], int n, int k) { // Count even numbers int even = 0; for ( int i = 0; i < n; i++) { // Check if the current // number is even if (arr[i] % 2 == 0) even++; } // Check if the even numbers to be // chosen is greater than n. Then, // there is no way to pick it. if (k > even) cout << 0 << endl; else { // Compute factorials on the fly long long numerator = 1; long long denominator = 1; for ( int i = even; i > even - k; i--) numerator *= i; for ( int i = 1; i <= k; i++) denominator *= i; // The number of ways will be nCk cout << numerator / denominator << endl; } } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 3, 4 }; int n = sizeof arr / sizeof arr[0]; // Given count of even elements int k = 1; // Function Call solve(arr, n, k); return 0; } // this code is contributed by bhardwajji |
Java
// Java program for the above approach import java.util.*; class Main { // Function to find the number of ways to // select exactly K even numbers // from the given array static void solve( int [] arr, int n, int k) { // Count even numbers int even = 0 ; for ( int i = 0 ; i < n; i++) { // Check if the current // number is even if (arr[i] % 2 == 0 ) even++; } // Check if the even numbers to be // chosen is greater than n. Then, // there is no way to pick it. if (k > even) System.out.println( 0 ); else { // Compute factorials on the fly long numerator = 1 ; long denominator = 1 ; for ( int i = even; i > even - k; i--) numerator *= i; for ( int i = 1 ; i <= k; i++) denominator *= i; // The number of ways will be nCk System.out.println(numerator / denominator); } } // Driver Code public static void main(String[] args) { // Given array arr[] int [] arr = { 1 , 2 , 3 , 4 }; int n = arr.length; // Given count of even elements int k = 1 ; // Function Call solve(arr, n, k); } } |
Python3
# Python program for the above approach import math # Function to find the number of ways to # select exactly K even numbers # from the given array def solve(arr, n, k): # Count even numbers even = 0 for i in range (n): # Check if the current # number is even if arr[i] % 2 = = 0 : even + = 1 # Check if the even numbers to be # chosen is greater than n. Then, # there is no way to pick it. if k > even: print ( 0 ) else : # Compute factorials on the fly numerator = 1 denominator = 1 for i in range (even, even - k, - 1 ): numerator * = i for i in range ( 1 , k + 1 ): denominator * = i # The number of ways will be nCk print ( int (numerator / denominator)) # Driver Code if __name__ = = "__main__" : # Given array arr[] arr = [ 1 , 2 , 3 , 4 ] n = len (arr) # Given count of even elements k = 1 # Function Call solve(arr, n, k) |
C#
using System; class GFG { // Function to find the number of ways to // select exactly K even numbers // from the given array static void Solve( int [] arr, int n, int k) { // Count even numbers int even = 0; for ( int i = 0; i < n; i++) { // Check if the current // number is even if (arr[i] % 2 == 0) even++; } // Check if the even numbers to be // chosen is greater than n. Then, // there is no way to pick it. if (k > even) Console.WriteLine(0); else { // Compute factorials on the fly long numerator = 1; long denominator = 1; for ( int i = even; i > even - k; i--) numerator *= i; for ( int i = 1; i <= k; i++) denominator *= i; // The number of ways will be nCk Console.WriteLine(numerator / denominator); } } // Driver Code public static void Main( string [] args) { // Given array arr[] int [] arr = { 1, 2, 3, 4 }; int n = arr.Length; // Given count of even elements int k = 1; // Function Call Solve(arr, n, k); } } |
Javascript
// Function to find the number of ways to // select exactly K even numbers // from the given array function solve(arr, n, k) { // Count even numbers let even = 0; for (let i = 0; i < n; i++) { // Check if the current // number is even if (arr[i] % 2 === 0) { even += 1; } } // Check if the even numbers to be // chosen is greater than n. Then, // there is no way to pick it. if (k > even) { console.log(0); } else { // Compute factorials on the fly let numerator = 1; let denominator = 1; for (let i = even; i > even - k; i--) { numerator *= i; } for (let i = 1; i <= k; i++) { denominator *= i; } // The number of ways will be nCk console.log(Math.floor(numerator / denominator)); } } // Driver Code const arr = [1, 2, 3, 4]; const n = arr.length; // Given count of even elements const k = 1; // Function Call solve(arr, n, k); |
Output
2
Time complexity : O(N)
Auxiliary Space : O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!