Dado un entero positivo N , la tarea es encontrar el número de enteros de N dígitos que tienen dígitos pares en índices impares y dígitos primos en índices pares.
Ejemplos:
Entrada: N = 2
Salida: 20
Explicación:
Los siguientes son el número posible de 2 dígitos que satisfacen los criterios dados {20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 50, 52, 54, 56, 58, 70, 72, 74, 76, 78}. Por lo tanto, la cuenta de tal número es 20.Entrada: N = 5
Salida: 1600
Enfoque: El problema dado se puede resolver utilizando el concepto de permutaciones y combinaciones al observar el hecho de que solo hay 4 opciones para las posiciones pares como [2, 3, 5, 7] y 5 opciones para las posiciones impares como [0, 2, 4, 6, 8] . Por lo tanto, el conteo de números de N dígitos que satisfacen los criterios dados viene dado por:
recuento total = 4 P 5 Q , donde P y Q son el número de posiciones pares e impares respectivamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approache #include<bits/stdc++.h> using namespace std; int m = 1000000007; // Function to find the value of x ^ y int power(int x, int y) { // Stores the value of x ^ y int res = 1; // Iterate until y is positive while (y > 0) { // If y is odd if ((y & 1) != 0) res = (res * x) % m; // Divide y by 2 y = y >> 1; x = (x * x) % m; } // Return the value of x ^ y return res; } // Function to find the number of N-digit // integers satisfying the given criteria int countNDigitNumber(int N) { // Count of even positions int ne = N / 2 + N % 2; // Count of odd positions int no = floor(N / 2); // Return the resultant count return power(4, ne) * power(5, no); } // Driver Code int main() { int N = 5; cout << countNDigitNumber(N) % m << endl; } // This code is contributed by SURENDRA_GANGWAR
Java
// Java program for the above approach import java.io.*; class GFG { static int m = 1000000007; // Function to find the value of x ^ y static int power(int x, int y) { // Stores the value of x ^ y int res = 1; // Iterate until y is positive while (y > 0) { // If y is odd if ((y & 1) != 0) res = (res * x) % m; // Divide y by 2 y = y >> 1; x = (x * x) % m; } // Return the value of x ^ y return res; } // Function to find the number of N-digit // integers satisfying the given criteria static int countNDigitNumber(int N) { // Count of even positions int ne = N / 2 + N % 2; // Count of odd positions int no = (int)Math.floor(N / 2); // Return the resultant count return power(4, ne) * power(5, no); } // Driver Code public static void main(String[] args) { int N = 5; System.out.println(countNDigitNumber(N) % m); } } // This code is contributed by sanjoy_62.
Python3
# Python program for the above approach import math m = 10**9 + 7 # Function to find the value of x ^ y def power(x, y): # Stores the value of x ^ y res = 1 # Iterate until y is positive while y > 0: # If y is odd if (y & 1) != 0: res = (res * x) % m # Divide y by 2 y = y >> 1 x = (x * x) % m # Return the value of x ^ y return res # Function to find the number of N-digit # integers satisfying the given criteria def countNDigitNumber(n: int) -> None: # Count of even positions ne = N // 2 + N % 2 # Count of odd positions no = N // 2 # Return the resultant count return power(4, ne) * power(5, no) # Driver Code if __name__ == '__main__': N = 5 print(countNDigitNumber(N) % m)
C#
// C# program for the above approach using System; class GFG{ static int m = 1000000007; // Function to find the value of x ^ y static int power(int x, int y) { // Stores the value of x ^ y int res = 1; // Iterate until y is positive while (y > 0) { // If y is odd if ((y & 1) != 0) res = (res * x) % m; // Divide y by 2 y = y >> 1; x = (x * x) % m; } // Return the value of x ^ y return res; } // Function to find the number of N-digit // integers satisfying the given criteria static int countNDigitNumber(int N) { // Count of even positions int ne = N / 2 + N % 2; // Count of odd positions int no = (int)Math.Floor((double)N / 2); // Return the resultant count return power(4, ne) * power(5, no); } // Driver Code public static void Main() { int N = 5; Console.Write(countNDigitNumber(N) % m); } } // This code is contributed by splevel62.
Javascript
<script> // JavaScript program for the above approache var m = 10 ** 9 + 7 // Function to find the value of x ^ y function power(x, y) { // Stores the value of x ^ y var res = 1 // Iterate until y is positive while (y > 0) { // If y is odd if ((y & 1) != 0) res = (res * x) % m // Divide y by 2 y = y >> 1 x = (x * x) % m } // Return the value of x ^ y return res } // Function to find the number of N-digit // integers satisfying the given criteria function countNDigitNumber(N) { // Count of even positions var ne = Math.floor(N / 2) + N % 2 // Count of odd positions var no = Math.floor(N / 2) // Return the resultant count return power(4, ne) * power(5, no) } // Driver Code let N = 5 document.write(countNDigitNumber(N) % m); // This code is contributed by Potta Lokesh </script>
1600
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por premansh2001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA