Recuento de permutaciones tales que la suma de K números del rango dado es par

Dado un rango [low, high] , ambos inclusive, y un número entero K , la tarea es seleccionar K números del rango (un número se puede elegir varias veces) de modo que la suma de esos K números sea par. Imprime el número de todas esas permutaciones.

Ejemplos:

Entrada: bajo = 4, alto = 5, k = 3 
Salida: 4 
Explicación: 
Hay 4 permutaciones válidas. Son {4, 4, 4}, {4, 5, 5}, {5, 4, 5} y {5, 5, 4} que suman un número par.

Entrada: bajo = 1, alto = 10, k = 2 
Salida: 50 
Explicación: 
Hay 50 permutaciones válidas. Son {1, 1}, {1, 3}, .. {1, 9} {2, 2}, {2, 4}, …, {2, 10}, …, {10, 2}, { 10, 4}, … {10, 10}. 
Estas 50 permutaciones, cada una suma un número par.

Enfoque ingenuo: la idea es encontrar todos los subconjuntos de tamaño K de modo que la suma del subconjunto sea par y también calcular la permutación para cada subconjunto requerido. 
Complejidad de Tiempo: O(K * (2 ^K )) 
Espacio Auxiliar: O(K)

Enfoque eficiente: la idea es utilizar el hecho de que la suma de dos números pares e impares siempre es par. Siga los pasos a continuación para resolver el problema:  

1. Encuentre el recuento total de números pares e impares en el rango dado [bajo, alto] .
2. Inicialice la variable even_sum = 1 y odd_sum = 0 para almacenar la forma de obtener la suma par y la suma impar respectivamente.
3. Itere un ciclo K veces y almacene la suma par anterior como prev_even = even_sum y la suma impar anterior como prev_odd = odd_sum where even_sum = (prev_even*even_count) + (prev_odd*odd_count) and odd_sum = (prev_par*odd_count) + (prev_odd* número_pares) .
4. Imprima la suma_par al final, ya que hay un conteo para la suma impar porque la suma_impar anterior contribuirá a la suma_par siguiente.

A continuación se muestra la implementación del enfoque anterior: 

// 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 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 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# 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

<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>

4

Complejidad temporal: O(K)
Espacio auxiliar: O(1)