# Count of permutations such that sum of K numbers from given range is even

Given a range **[low, high]**, both inclusive, and an integer **K**, the task is to select **K** numbers from the range(a number can be chosen multiple times) such that the sum of those **K** numbers is even. Print the number of all such permutations.

**Examples:**

Input:low = 4, high = 5, k = 3Output:4Explanation:

There are 4 valid permutation. They are {4, 4, 4}, {4, 5, 5}, {5, 4, 5} and {5, 5, 4} which sum up to an even number.

Input:low = 1, high = 10, k = 2Output:50Explanation:

There are 50 valid permutations. They are {1, 1}, {1, 3}, .. {1, 9} {2, 2}, {2, 4}, …, {2, 10}, …, {10, 2}, {10, 4}, … {10, 10}.

These 50 permutations, each sum up to an even number.

**Naive Approach:** The idea is to find all subset of size K such that the sum of the subset is even and also calculate permutation for each required subset. **Time Complexity:** O(K * (2^{K})) **Auxiliary Space:** O(K)

**Efficient Approach:** The idea is to use the fact that the sum of two even and odd numbers is always even. Follow the steps below to solve the problem:

- Find the total count of even and odd numbers in the given range
**[low, high]**. - Initialize variable
**even_sum = 1**and**odd_sum = 0**to store way to get even sum and odd sum respectively. - Iterate a loop
**K**times and store the previous even sum as**prev_even = even_sum**and the previous odd sum as**prev_odd = odd_sum**where**even_sum = (prev_even*even_count) + (prev_odd*odd_count)**and**odd_sum = (prev_even*odd_count) + (prev_odd*even_count)**. - Print the even_sum at the end as there is a count for the odd sum because the previous odd_sum will contribute to the next even_sum.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include<bits/stdc++.h>` `using` `namespace` `std;` `// Function to return the number` `// of all permutations such that` `// sum of K numbers in range is even` `int` `countEvenSum(` `int` `low, ` `int` `high, ` `int` `k)` `{` ` ` ` ` `// Find total count of even and` ` ` `// odd number in given range` ` ` `int` `even_count = high / 2 - (low - 1) / 2;` ` ` `int` `odd_count = (high + 1) / 2 - low / 2;` ` ` `long` `even_sum = 1;` ` ` `long` `odd_sum = 0;` ` ` `// Iterate loop k times and update` ` ` `// even_sum & odd_sum using` ` ` `// previous values` ` ` `for` `(` `int` `i = 0; i < k; i++)` ` ` `{` ` ` ` ` `// Update the prev_even and` ` ` `// odd_sum` ` ` `long` `prev_even = even_sum;` ` ` `long` `prev_odd = odd_sum;` ` ` `// Even sum` ` ` `even_sum = (prev_even * even_count) +` ` ` `(prev_odd * odd_count);` ` ` `// Odd sum` ` ` `odd_sum = (prev_even * odd_count) +` ` ` `(prev_odd * even_count);` ` ` `}` ` ` `// Return even_sum` ` ` `cout << (even_sum);` `}` `// Driver Code` `int` `main()` `{` ` ` ` ` `// Given ranges` ` ` `int` `low = 4;` ` ` `int` `high = 5;` ` ` `// Length of permutation` ` ` `int` `K = 3;` ` ` ` ` `// Function call` ` ` `countEvenSum(low, high, K);` `}` `// This code is contributed by Stream_Cipher` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG {` ` ` `// Function to return the number` ` ` `// of all permutations such that` ` ` `// sum of K numbers in range is even` ` ` `public` `static` `void` ` ` `countEvenSum(` `int` `low, ` `int` `high,` ` ` `int` `k)` ` ` `{` ` ` `// Find total count of even and` ` ` `// odd number in given range` ` ` `int` `even_count = high / ` `2` `- (low - ` `1` `) / ` `2` `;` ` ` `int` `odd_count = (high + ` `1` `) / ` `2` `- low / ` `2` `;` ` ` `long` `even_sum = ` `1` `;` ` ` `long` `odd_sum = ` `0` `;` ` ` `// Iterate loop k times and update` ` ` `// even_sum & odd_sum using` ` ` `// previous values` ` ` `for` `(` `int` `i = ` `0` `; i < k; i++) {` ` ` `// Update the prev_even and` ` ` `// odd_sum` ` ` `long` `prev_even = even_sum;` ` ` `long` `prev_odd = odd_sum;` ` ` `// Even sum` ` ` `even_sum = (prev_even * even_count)` ` ` `+ (prev_odd * odd_count);` ` ` `// Odd sum` ` ` `odd_sum = (prev_even * odd_count)` ` ` `+ (prev_odd * even_count);` ` ` `}` ` ` `// Return even_sum` ` ` `System.out.println(even_sum);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `// Given ranges` ` ` `int` `low = ` `4` `;` ` ` `int` `high = ` `5` `;` ` ` `// Length of permutation` ` ` `int` `K = ` `3` `;` ` ` `// Function call` ` ` `countEvenSum(low, high, K);` ` ` `}` `}` |

## Python3

`# Python3 program for the above approach` `# Function to return the number` `# of all permutations such that` `# sum of K numbers in range is even` `def` `countEvenSum(low, high, k):` ` ` `# Find total count of even and` ` ` `# odd number in given range` ` ` `even_count ` `=` `high ` `/` `2` `-` `(low ` `-` `1` `) ` `/` `2` ` ` `odd_count ` `=` `(high ` `+` `1` `) ` `/` `2` `-` `low ` `/` `2` ` ` `even_sum ` `=` `1` ` ` `odd_sum ` `=` `0` ` ` `# Iterate loop k times and update` ` ` `# even_sum & odd_sum using` ` ` `# previous values` ` ` `for` `i ` `in` `range` `(` `0` `, k):` ` ` ` ` `# Update the prev_even and` ` ` `# odd_sum` ` ` `prev_even ` `=` `even_sum` ` ` `prev_odd ` `=` `odd_sum` ` ` `# Even sum` ` ` `even_sum ` `=` `((prev_even ` `*` `even_count) ` `+` ` ` `(prev_odd ` `*` `odd_count))` ` ` `# Odd sum` ` ` `odd_sum ` `=` `((prev_even ` `*` `odd_count) ` `+` ` ` `(prev_odd ` `*` `even_count))` ` ` `# Return even_sum` ` ` `print` `(` `int` `(even_sum))` `# Driver Code` `# Given ranges` `low ` `=` `4` `;` `high ` `=` `5` `;` `# Length of permutation` `K ` `=` `3` `;` `# Function call` `countEvenSum(low, high, K);` `# This code is contributed by Stream_Cipher` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `// Function to return the number` `// of all permutations such that` `// sum of K numbers in range is even` `public` `static` `void` `countEvenSum(` `int` `low,` ` ` `int` `high, ` `int` `k)` `{` ` ` ` ` `// Find total count of even and` ` ` `// odd number in given range` ` ` `int` `even_count = high / 2 - (low - 1) / 2;` ` ` `int` `odd_count = (high + 1) / 2 - low / 2;` ` ` `long` `even_sum = 1;` ` ` `long` `odd_sum = 0;` ` ` `// Iterate loop k times and update` ` ` `// even_sum & odd_sum using` ` ` `// previous values` ` ` `for` `(` `int` `i = 0; i < k; i++)` ` ` `{` ` ` ` ` `// Update the prev_even and` ` ` `// odd_sum` ` ` `long` `prev_even = even_sum;` ` ` `long` `prev_odd = odd_sum;` ` ` `// Even sum` ` ` `even_sum = (prev_even * even_count) +` ` ` `(prev_odd * odd_count);` ` ` `// Odd sum` ` ` `odd_sum = (prev_even * odd_count) +` ` ` `(prev_odd * even_count);` ` ` `}` ` ` `// Return even_sum` ` ` `Console.WriteLine(even_sum);` `}` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` ` ` `// Given ranges` ` ` `int` `low = 4;` ` ` `int` `high = 5;` ` ` `// Length of permutation` ` ` `int` `K = 3;` ` ` `// Function call` ` ` `countEvenSum(low, high, K);` `}` `}` `// This code is contributed by amal kumar choubey` |

## Javascript

`<script>` `// JavaScript program for the above approach` ` ` `// Function to return the number` ` ` `// of all permutations such that` ` ` `// sum of K numbers in range is even` ` ` `function` ` ` `countEvenSum(low, high, k)` ` ` `{` ` ` `// Find total count of even and` ` ` `// odd number in given range` ` ` `let even_count = high / 2 - (low - 1) / 2;` ` ` `let odd_count = (high + 1) / 2 - low / 2;` ` ` ` ` `let even_sum = 1;` ` ` `let odd_sum = 0;` ` ` ` ` `// Iterate loop k times and update` ` ` `// even_sum & odd_sum using` ` ` `// previous values` ` ` `for` `(let i = 0; i < k; i++) {` ` ` ` ` `// Update the prev_even and` ` ` `// odd_sum` ` ` `let prev_even = even_sum;` ` ` `let prev_odd = odd_sum;` ` ` ` ` `// Even sum` ` ` `even_sum = (prev_even * even_count)` ` ` `+ (prev_odd * odd_count);` ` ` ` ` `// Odd sum` ` ` `odd_sum = (prev_even * odd_count)` ` ` `+ (prev_odd * even_count);` ` ` `}` ` ` ` ` `// Return even_sum` ` ` `document.write(even_sum);` ` ` `}` `// Driver Code` ` ` `// Given ranges` ` ` `let low = 4;` ` ` `let high = 5;` ` ` ` ` `// Length of permutation` ` ` `let K = 3;` ` ` ` ` `// Function call` ` ` `countEvenSum(low, high, K);` ` ` `</script>` |

**Output:**

4

**Time Complexity:** O(K)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**