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