Given an array arr[] of size N. The task is to find the minimum number of swaps required to re-arrange the array such that all prime-indexed elements are prime, If the task can’t be achieved, print “-1“
Examples:
Input: N = 5, arr[] = {1, 2, 3, 4, 5}
Output: 0
Explanation: All the prime indices {2, 3, 5} (one-based indexing) have prime elements present on them. Therefore, minimum swaps required is 0.Input: N = 5, arr[] = {2, 7, 8, 5, 13}
Output: 1
Explanation: swap 8 and 5 once, to get all the prime numbers at prime indices.
Approach: The task can be solved using the Sieve of Eratosthenes.
- Iterate over the array and check whether the current index is prime or not, if it is a prime, check the element present on this index.
- On observation, it can be seen that It is possible to achieve the required configuration, only if the total number of primes in the array is greater than or equal to the total number of prime indices in the array.
- If this condition holds, then the minimum number of swaps is equal to the number of prime indices that do not have a prime number on them.
Below is the implementation of the above approach:
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 notvoid 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 requiredint 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 Codeint 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 approachimport 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 approachimport mathmxn = 10000 + 1prime = [True for _ in range(mxn + 1)]# Function to pre-calculate the prime[]# prime[i] denotes whether# i is prime or notdef 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 requireddef 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 Codeif __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 approachusing 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 notfunction 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 requiredfunction 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> |
Output
1
Time Complexity: O(mxn(log(log(mxn)))
Auxiliary Space: O(mxn)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
