Recuento de números de longitud N que tienen números primos en índices impares y números impares en índices pares

Dado un número N , la tarea es calcular el número de números de longitud N que tienen números primos en índices impares y números impares en índices pares .

Ejemplo :

Entrada : N = 1
Salida : 5
Explicación : Todos los números válidos de longitud 1 son 1, 3, 5, 7, 9, aquí tenemos solo 1 índice impar, por lo tanto, tenemos 5 números válidos.

Entrada : N = 2
Salida : 20 
Explicación: Hay 20 números válidos de longitud 2.

Enfoque : El problema se puede resolver con la ayuda de la combinatoria . Los dígitos en índices impares tienen 4 opciones y los dígitos en índices pares tienen 5 opciones.
Siga los pasos para resolver el problema:

• Hay 5 opciones para índices pares (1, 3, 5, 7, 9) y 4 opciones para índices impares (2, 3, 5, 7).
• Para un número de longitud N, habrá N/2 índices impares y ( N/2 + N%2 ) índices pares.
• Entonces, el número de formas de llenar N/2 índices impares es   4 ^N/2 .
• Y el número de formas de llenar índices pares es   5 ^{(N/2 + N%2)} .
• Por lo tanto, la cuenta total de todos los números válidos será 4 ^N/2  * 5 ^{(N/2 + N%2)} .

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

// c++ program to Count of numbers of length
// N having prime numbers at odd indices and
// odd numbers at even indices
#include<bits/stdc++.h>
using namespace std;
// function to find total number of ways
int find_Numb_ways(int n)
{
    // No of odd indices in n-digit number
    int odd_indices = n/2;
   
    // No of even indices in n-digit number
    int even_indices = (n / 2) + (n % 2);
   
    //  No of ways of arranging prime number
    //  digits in odd indices
    int arr_odd = pow(4, odd_indices);
   
    //   No of ways of arranging odd number
    //  digits in even indices
    int arr_even = pow(5, even_indices);
   
    // returning the total number of ways
    return arr_odd * arr_even;
}
 
// drive code
int main()
{
    int n = 4;
    cout << find_Numb_ways(n) << endl;
    return 0;
}
 
// This code is contributed by kondamrohan02.

// Java program to Count of numbers of length
// N having prime numbers at odd indices and
// odd numbers at even indices
import java.util.*;
 
class GFG
{
 
// function to find total number of ways
static int find_Numb_ways(int n)
{
   
    // No of odd indices in n-digit number
    int odd_indices = n/2;
   
    // No of even indices in n-digit number
    int even_indices = (n / 2) + (n % 2);
   
    //  No of ways of arranging prime number
    //  digits in odd indices
    int arr_odd = (int)Math.pow(4, odd_indices);
   
    //   No of ways of arranging odd number
    //  digits in even indices
    int arr_even = (int)Math.pow(5, even_indices);
   
    // returning the total number of ways
    return arr_odd * arr_even;
}
 
    // Driver Code
    public static void main(String[] args) {
        int n = 4;
     System.out.print(find_Numb_ways(n));
 
    }
}
 
// This code is contributed by code_hunt.

# python program for above approach
def count(N):
 
    # No of odd indices in N-digit number
    odd_indices = N//2
 
    # No of even indices in N-digit number
    even_indices = N//2 + N % 2
 
    # No of ways of arranging prime number
    # digits in odd indices
    arrange_odd = 4 ** odd_indices
 
    # No of ways of arranging odd number
    # digits in even indices
    arrange_even = 5 ** even_indices
 
    # returning the total number of ways
    return arrange_odd * arrange_even
 
 
# Driver code
if __name__ == "__main__":
 
    N = 4
    # calling the function
    print(count(N))

// C# program to Count of numbers of length
// N having prime numbers at odd indices and
// odd numbers at even indices
using System;
using System.Collections.Generic;
 
class GFG{
 
// function to find total number of ways
static int find_Numb_ways(int n)
{
    // No of odd indices in n-digit number
    int odd_indices = n/2;
   
    // No of even indices in n-digit number
    int even_indices = (n / 2) + (n % 2);
   
    //  No of ways of arranging prime number
    //  digits in odd indices
    int arr_odd = (int)Math.Pow(4, odd_indices);
   
    //   No of ways of arranging odd number
    //  digits in even indices
    int arr_even = (int)Math.Pow(5, even_indices);
   
    // returning the total number of ways
    return arr_odd * arr_even;
}
 
// drive code
public static void Main()
{
    int n = 4;
    Console.Write(find_Numb_ways(n));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
 
// Javascript program to Count of numbers of length
// N having prime numbers at odd indices and
// odd numbers at even indices
 
// function to find total number of ways
function find_Numb_ways(n)
{
    // No of odd indices in n-digit number
    var odd_indices = n/2;
 
    // No of even indices in n-digit number
    var even_indices = (n / 2) + (n % 2);
   
    //  No of ways of arranging prime number
    //  digits in odd indices
    var arr_odd = Math.pow(4, odd_indices);
   
    //   No of ways of arranging odd number
    //  digits in even indices
    var arr_even = Math.pow(5, even_indices);
   
    // returning the total number of ways
    return arr_odd * arr_even;
}
 
// drive code
    var n = 4;
    document.write(find_Numb_ways(n));
 
// This code is contributed by ipg2016107.
</script>

400

Complejidad de tiempo : O(1), (operaciones de tiempo constante)
Espacio auxiliar : O(1), (no se requiere espacio adicional)