Dada una array arr[] de tamaño N. La tarea es encontrar el número mínimo de intercambios necesarios para reorganizar la array de modo que todos los elementos indexados primos sean primos . Si no se puede lograr la tarea, imprima » -1 “
Ejemplos:
Entrada : N = 5, arr[] = {1, 2, 3, 4, 5}
Salida : 0
Explicación : Todos los índices primos {2, 3, 5} (indexación basada en uno) tienen elementos primos presentes en ellos. Por lo tanto, los intercambios mínimos requeridos son 0.Entrada : N = 5, arr[] = {2, 7, 8, 5, 13}
Salida : 1
Explicación : intercambie 8 y 5 una vez, para obtener todos los números primos en índices primos.
Planteamiento: La tarea se puede resolver usando el Tamiz de Eratóstenes .
- Itere sobre la array y verifique si el índice actual es primo o no, si es primo, verifique el elemento presente en este índice.
- En la observación, se puede ver que es posible lograr la configuración requerida, solo si el número total de primos en la array es mayor o igual que el número total de índices primos en la array.
- Si esta condición se cumple, entonces el número mínimo de swaps es igual al número de índices primos que no tienen un número primo.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h> using namespace std; const int mxn = 1e4 + 1; bool prime[mxn + 1]; // Function to pre-calculate the prime[] // prime[i] denotes whether // i is prime or not void SieveOfEratosthenes() { memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= mxn; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of p greater than or // equal to the square of it // numbers which are multiple // of p and are less than p^2 // are already been marked. for (int i = p * p; i <= mxn; i += p) prime[i] = false; } } } // Function to count minimum number // of swaps required int countMin(int arr[], int n) { // To count the minimum number of swaps // required to convert the array into // perfectly prime int cMinSwaps = 0; // To count total number of prime // indexes in the array int cPrimeIndices = 0; // To count the total number of // prime numbers in the array int cPrimeNos = 0; for (int i = 0; i < n; i++) { // Check whether index // is prime or not if (prime[i + 1]) { cPrimeIndices++; // Element is not prime if (!prime[arr[i]]) cMinSwaps++; else cPrimeNos++; } else if (prime[arr[i]]) { cPrimeNos++; } } // If the total number of prime numbers // is greater than or equal to the total // number of prime indices, then it is // possible to convert the array into // perfectly prime if (cPrimeNos >= cPrimeIndices) return cMinSwaps; else return -1; } // Driver Code int main() { // Pre-calculate prime[] SieveOfEratosthenes(); int n = 5; int arr[5] = { 2, 7, 8, 5, 13 }; cout << countMin(arr, n); return 0; }
Java
// Java program for the above approach import java.io.*; class GFG { static boolean prime[] = new boolean[(int)1e4 + 2]; static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value in // prime[i] will finally be false if i is Not a // prime, else true. for (int i = 0; i < (int)1e4 + 2; i++) prime[i] = true; for (int p = 2; p * p < (int)1e4 + 2; p++) { // If prime[p] is not changed, then it is a // prime if (prime[p] == true) { // Update all multiples of p for (int i = p * p; i < (int)1e4 + 2; i += p) prime[i] = false; } } } // Function to count minimum number // of swaps required static int countMin(int[] arr, int n) { // To count the minimum number of swaps // required to convert the array into // perfectly prime int cMinSwaps = 0; // To count total number of prime // indexes in the array int cPrimeIndices = 0; // To count the total number of // prime numbers in the array int cPrimeNos = 0; for (int i = 0; i < n; i++) { // Check whether index // is prime or not if (prime[i + 1]) { cPrimeIndices++; // Element is not prime if (prime[arr[i]] == false) cMinSwaps++; else cPrimeNos++; } else if (prime[arr[i]]) { cPrimeNos++; } } // If the total number of prime numbers // is greater than or equal to the total // number of prime indices, then it is // possible to convert the array into // perfectly prime if (cPrimeNos >= cPrimeIndices) return cMinSwaps; else return -1; } // Driver Code public static void main(String[] args) { // Pre-calculate prime[] SieveOfEratosthenes(); int n = 5; int arr[] = { 2, 7, 8, 5, 13 }; System.out.println(countMin(arr, n)); } } // This code is contributed by Potta Lokesh
Python3
# Python program for the above approach import math mxn = 10000 + 1 prime = [True for _ in range(mxn + 1)] # Function to pre-calculate the prime[] # prime[i] denotes whether # i is prime or not def SieveOfEratosthenes(): global prime for p in range(2, int(math.sqrt(mxn)) + 1): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples # of p greater than or # equal to the square of it # numbers which are multiple # of p and are less than p^2 # are already been marked. for i in range(p*p, mxn+1, p): prime[i] = False # Function to count minimum number # of swaps required def countMin(arr, n): # To count the minimum number of swaps # required to convert the array into # perfectly prime cMinSwaps = 0 # To count total number of prime # indexes in the array cPrimeIndices = 0 # To count the total number of # prime numbers in the array cPrimeNos = 0 for i in range(0, n): # Check whether index # is prime or not if (prime[i + 1]): cPrimeIndices += 1 # Element is not prime if (not prime[arr[i]]): cMinSwaps += 1 else: cPrimeNos += 1 elif (prime[arr[i]]): cPrimeNos += 1 # If the total number of prime numbers # is greater than or equal to the total # number of prime indices, then it is # possible to convert the array into # perfectly prime if (cPrimeNos >= cPrimeIndices): return cMinSwaps else: return -1 # Driver Code if __name__ == "__main__": # Pre-calculate prime[] SieveOfEratosthenes() n = 5 arr = [2, 7, 8, 5, 13] print(countMin(arr, n)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach using System; class GFG { static bool[] prime = new bool[(int)1e4 + 2]; static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value in // prime[i] will finally be false if i is Not a // prime, else true. for (int i = 0; i < (int)1e4 + 2; i++) prime[i] = true; for (int p = 2; p * p < (int)1e4 + 2; p++) { // If prime[p] is not changed, then it is a // prime if (prime[p] == true) { // Update all multiples of p for (int i = p * p; i < (int)1e4 + 2; i += p) prime[i] = false; } } } // Function to count minimum number // of swaps required static int countMin(int[] arr, int n) { // To count the minimum number of swaps // required to convert the array into // perfectly prime int cMinSwaps = 0; // To count total number of prime // indexes in the array int cPrimeIndices = 0; // To count the total number of // prime numbers in the array int cPrimeNos = 0; for (int i = 0; i < n; i++) { // Check whether index // is prime or not if (prime[i + 1]) { cPrimeIndices++; // Element is not prime if (prime[arr[i]] == false) cMinSwaps++; else cPrimeNos++; } else if (prime[arr[i]]) { cPrimeNos++; } } // If the total number of prime numbers // is greater than or equal to the total // number of prime indices, then it is // possible to convert the array into // perfectly prime if (cPrimeNos >= cPrimeIndices) return cMinSwaps; else return -1; } // Driver Code public static void Main() { // Pre-calculate prime[] SieveOfEratosthenes(); int n = 5; int[] arr = { 2, 7, 8, 5, 13 }; Console.Write(countMin(arr, n)); } } // This code is contributed by subhammahato348.
Javascript
<script> const mxn = 1e4 + 1; let prime = new Array(mxn + 1); // Function to pre-calculate the prime[] // prime[i] denotes whether // i is prime or not function SieveOfEratosthenes() { prime.fill(true); for (let p = 2; p * p <= mxn; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of p greater than or // equal to the square of it // numbers which are multiple // of p and are less than p^2 // are already been marked. for (let i = p * p; i <= mxn; i += p) prime[i] = false; } } } // Function to count minimum number // of swaps required function countMin(arr, n) { // To count the minimum number of swaps // required to convert the array into // perfectly prime let cMinSwaps = 0; // To count total number of prime // indexes in the array let cPrimeIndices = 0; // To count the total number of // prime numbers in the array let cPrimeNos = 0; for (let i = 0; i < n; i++) { // Check whether index // is prime or not if (prime[i + 1]) { cPrimeIndices++; // Element is not prime if (!prime[arr[i]]) cMinSwaps++; else cPrimeNos++; } else if (prime[arr[i]]) { cPrimeNos++; } } // If the total number of prime numbers // is greater than or equal to the total // number of prime indices, then it is // possible to convert the array into // perfectly prime if (cPrimeNos >= cPrimeIndices) return cMinSwaps; else return -1; } // Driver Code // Pre-calculate prime[] SieveOfEratosthenes(); let n = 5; let arr = [2, 7, 8, 5, 13]; document.write(countMin(arr, n)); // This code is contributed by gfgking. </script>
1
Complejidad de tiempo : O(mxn(log(log(mxn)))
Espacio auxiliar : O(mxn)
Publicación traducida automáticamente
Artículo escrito por vishnuthulasidosss y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA