Dado un número entero N , la tarea es encontrar el número de permutaciones de los primeros N números enteros positivos tales que los números primos estén en índices primos (para la indexación basada en 1).
Nota: Dado que el número de vías puede ser muy grande, devuelva la respuesta módulo 10 9 + 7.
Ejemplos:
Entrada: N = 3
Salida: 2
Explicación:
Posible permutación de los primeros 3 enteros positivos, de modo que los números primos estén en índices primos: {1, 2, 3}, {1, 3, 2}
Entrada: N = 5
Salida: 12
Explicación :
algunas de las permutaciones posibles de los primeros 5 enteros positivos, de modo que los números primos están en índices primos son: {1, 2, 3, 4}, {1, 3, 2, 4}, {4, 2, 3 , 1}, {4, 3, 2, 1}
Enfoque: hay K números primos de 1 a N y hay exactamente K números de índices primos de índice 1 a N. Entonces, el número de permutaciones para números primos es K!. De manera similar, el número de permutaciones para números no primos es (NK)!. ¡Entonces el número total de permutaciones es K!*(NK)!
Por ejemplo:
Given test case: [1,2,3,4,5].
2, 3 and 5 are fixed on prime index slots,
we can only swap them around.
There are 3 x 2 x 1 = 3! ways
[[2,3,5], [2,5,3], [3,2,5],
[3,5,2], [5,2,3], [5,3,2]],
For Non-prime numbers - {1,4}
[[1,4], [4,1]]
So the total is 3!*2!
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// permutation of first N positive
// integers such that prime numbers
// are at the prime indices
#define mod 1000000007
#include<bits/stdc++.h>
using namespace std;
int fact(int n)
{
int ans = 1;
while(n > 0)
{
ans = ans * n;
n--;
}
return ans;
}
// Function to check that
// a number is prime or not
bool isPrime(int n)
{
if(n <= 1)
return false;
// Loop to check that
// number is divisible by any
// other number or not except 1
for(int i = 2; i< sqrt(n) + 1; i++)
{
if(n % i == 0)
return false;
else
return true;
}
}
// Function to find the permutations
void findPermutations(int n)
{
int prime = 0;
// Loop to find the
// number of prime numbers
for(int j = 1; j < n + 1; j++)
{
if(isPrime(j))
prime += 1;
}
// Permutation of N
// positive integers
int W = fact(prime) * fact(n - prime);
cout << (W % mod);
}
// Driver Code
int main()
{
int n = 7;
findPermutations(n);
}
// This code is contributed by Bhupendra_Singh
Java
// Java implementation to find the
// permutation of first N positive
// integers such that prime numbers
// are at the prime indices
import java.io.*;
class GFG{
static int mod = 1000000007;
static int fact(int n)
{
int ans = 1;
while(n > 0)
{
ans = ans * n;
n--;
}
return ans;
}
// Function to check that
// a number is prime or not
static boolean isPrime(int n)
{
if(n <= 1)
return false;
// Loop to check that
// number is divisible by any
// other number or not except 1
for(int i = 2; i< Math.sqrt(n) + 1; i++)
{
if(n % i == 0)
return false;
else
return true;
}
return true;
}
// Function to find the permutations
static void findPermutations(int n)
{
int prime = 0;
// Loop to find the
// number of prime numbers
for(int j = 1; j < n + 1; j++)
{
if(isPrime(j))
prime += 1;
}
// Permutation of N
// positive integers
int W = fact(prime) * fact(n - prime);
System.out.println(W % mod);
}
// Driver Code
public static void main (String[] args)
{
int n = 7;
findPermutations(n);
}
}
// This code is contributed by shubhamsingh10
Python3
# Python3 implementation to find the # permutation of first N positive # integers such that prime numbers # are at the prime indices import math # Function to check that # a number is prime or not def isPrime(n): if n <= 1: return False # Loop to check that # number is divisible by any # other number or not except 1 for i in range(2, int(n**0.5)+1): if n % i == 0: return False else: return True # Constant value for modulo CONST = int(math.pow(10, 9))+7 # Function to find the permutations def findPermutations(n): prime = 0 # Loop to find the # number of prime numbers for j in range (1, n + 1): if isPrime(j): prime+= 1 # Permutation of N # positive integers W = math.factorial(prime)*\ math.factorial(n-prime) print (W % CONST) # Driver Code if __name__ == "__main__": n = 7 # Function Call findPermutations(n)
C#
// C# implementation to find the
// permutation of first N positive
// integers such that prime numbers
// are at the prime indices
using System;
class GFG{
static int mod = 1000000007;
static int fact(int n)
{
int ans = 1;
while(n > 0)
{
ans = ans * n;
n--;
}
return ans;
}
// Function to check that
// a number is prime or not
static bool isPrime(int n)
{
if(n <= 1)
return false;
// Loop to check that
// number is divisible by any
// other number or not except 1
for(int i = 2; i < Math.Sqrt(n) + 1; i++)
{
if(n % i == 0)
return false;
else
return true;
}
return true;
}
// Function to find the permutations
static void findPermutations(int n)
{
int prime = 0;
// Loop to find the
// number of prime numbers
for(int j = 1; j < n + 1; j++)
{
if(isPrime(j))
prime += 1;
}
// Permutation of N
// positive integers
int W = fact(prime) * fact(n - prime);
Console.Write(W % mod);
}
// Driver Code
public static void Main()
{
int n = 7;
findPermutations(n);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// JavaScript implementation to find the
// permutation of first N positive
// integers such that prime numbers
// are at the prime indices
let mod = 1000000007;
function fact(n)
{
let ans = 1;
while(n > 0)
{
ans = ans * n;
n--;
}
return ans;
}
// Function to check that
// a number is prime or not
function isPrime(n)
{
if(n <= 1)
return false;
// Loop to check that
// number is divisible by any
// other number or not except 1
for(let i = 2; i< Math.sqrt(n) + 1; i++)
{
if(n % i == 0)
return false;
else
return true;
}
}
// Function to find the permutations
function findPermutations(n)
{
let prime = 0;
// Loop to find the
// number of prime numbers
for(let j = 1; j < n + 1; j++)
{
if(isPrime(j))
prime += 1;
}
// Permutation of N
// positive integers
let W = fact(prime) * fact(n - prime);
document.write(W % mod);
}
// Driver Code
let n = 7;
findPermutations(n);
// This code is contributed by Manoj.
</script>
Salida:
144
144
Complejidad del tiempo: O(n 3/2 )
Espacio Auxiliar: O(1)