Intuition
There are two intuitions that would help us to solve this problem:
For the answer to exist, we need to realize that the number of prime numbers stored in the array should be greater than or equal to the number of total prime indices.
As the swaps are always done between the prime and composite numbers, there is only one way to count the number of swaps. Whenever we find a composite number at the prime index, we need to swap it with a prime number and increase the count of the number of swaps.
The further approach can be understood below.
Also see, Euclid GCD Algorithm
Approach
According to intuition, first, we need to count the number of prime indices and prime elements in the array ‘NUMS’. If prime elements are greater than or equal to prime indices, we will start counting the number of swaps. The problem can be solved with the help of below two functions:
- Function isPrime(int n) will be used to find if the number ‘n’ is prime or not.
- Function countSwaps() will be used to count the required number of swaps as discussed above.
The implementation can be found in the below program.
Program
// Program to find the minimum number of swaps to rearrange the array.
#include <iostream>
#include <vector>
using namespace std;
// Function to find if 'N' is a prime number.
bool isPrime(int n)
{
// 1 is neither a prime nor a composite number.
if (n == 1)
return false;
// If the divisor is not found till root 'N', then 'N' is prime.
for (int i = 2; i * i <= n; i++)
{
// If the divisor is found.
if (n % i == 0)
return false;
}
// Any divisor is not found, so prime.
return true;
}
// Function to count the number of swaps to rearrange the array.
int countSwaps(vector<int>& NUMS, int N)
{
// Variables to store the count of prime indices and elements, respectively.
int cntInd = 0, cntEle = 0;
// Variable to store the count of swaps.
int swaps = 0;
// Iterating the array to find if the index is prime, but the element is composite.
for (int i = 1; i <= N; i++)
{
// Finding if the index is prime.
bool isIndPrime = isPrime(i);
if (isIndPrime)
cntInd++;
// Finding if the element is prime.
bool isElePrime = isPrime(NUMS[i - 1]);
if (isElePrime)
cntEle++;
// If the index is prime but the element is not prime, increase the swaps.
if (isIndPrime && !isElePrime)
swaps++;
}
// If the prime indices are less than or equal to prime elements, return the swaps.
if (cntInd <= cntEle)
return swaps;
else
{
// If the prime indices are greater than prime elements, then the answer doesn't exist.
return -1;
}
}
// Main function.
int main()
{
// Size of the vector NUMS.
int N; cin >> N;
// Input the vector NUMS.
vector<int> NUMS(N);
for (int i = 0; i < N; i++)
cin >> NUMS[i];
// Calculating the answer.
int ans = countSwaps(NUMS, N);
// Output answer.
if (ans == -1)
cout << "Not Possible";
else
cout << "Number of swaps required are: " << ans;
return 0;
}
Example
Input
4
2 3 4 4
Output
Number of swaps required are: 1
Complexity Analysis
Time Complexity: O(N X √M), where ‘N’ is the size and ‘M’ is the maximum element of the array ‘NUMS’.
Explanation:
In function countSwaps(), while traversing the array, we are checking for every element if it is prime in √NUMS[i] time which sums up to O(N X √M).
Auxiliary Space: O(1)
Explanation: No extra space is used.
With Sieve of Eratosthenes
In the above program, the function isPrime(int N) takes a total of √N time to check if ‘N’ is prime. With the Sieve of Eratosthenes, we can mark every element in the range as the prime or composite.
Below is the implementation of the above program with the help of Sieve Of Eratosthenes.
Program
// Program to find the minimum number of swaps to rearrange the array.
#include <iostream>
#include <vector>
using namespace std;
// The range of elements.
int M = 1e5 + 1;
// Vector to store primality of numbers.
vector<bool> isPrime;
// Function to run Sieve of Eratosthenes.
void sieveOfEratosthenes()
{
isPrime = vector<bool>(M, true);
// 1 is neither a prime nor a composite number.
isPrime[1] = false;
for (int i = 2; i * i <= M; i++)
{
// If the element is not prime, then continue.
if (!isPrime[i])
continue;
// Updating the multiples of i, as they are not prime.
for (int j = i * i; j <= M; j += i)
isPrime[j] = false;
}
}
// Function to count the number of swaps to rearrange the array.
int countSwaps(vector<int>& NUMS, int N)
{
// Variables to store the count of prime indices and elements, respectively.
int cntInd = 0, cntEle = 0;
// Variable to store the count of swaps.
int swaps = 0;
// Iterating the array to find if the index is prime, frequently asked but the element is composite.
for (int i = 1; i <= N; i++)
{
// Finding if the index is prime.
bool isIndPrime = isPrime[i];
if (isIndPrime)
cntInd++;
// Finding if the element is prime.
bool isElePrime = isPrime[NUMS[i - 1]];
if (isElePrime)
cntEle++;
// If the index is prime but the element is not prime, increase the swaps.
if (isIndPrime && !isElePrime)
swaps++;
}
// If the prime indices are less than or equal to prime elements, return the swaps.
if (cntInd <= cntEle)
return swaps;
else
{
// If the prime indices are greater than prime elements, then the answer doesn't exist.
return -1;
}
}
// Main function.
int main()
{
// Size of the vector NUMS.
int N; cin >> N;
// Input of the vector NUMS.
vector<int> NUMS(N);
for (int i = 0; i < N; i++)
cin >> NUMS[i];
M = (*max_element(NUMS.begin(), NUMS.end())) + 1;
// Precomputing primes using the Sieve Of Eratosthenes.
sieveOfEratosthenes();
// Calculating the answer.
int ans = countSwaps(NUMS, N);
// Output answer.
if (ans == -1)
cout << "Not Possible";
else
cout << "Number of Swaps required are: " << ans;
return 0;
}
Example
Input
6
2 1 4 3 8 5
Output
Number of Swaps required are: 3
Complexity Analysis
Time Complexity: O(M X (log(log(M)))), where ‘M’ is the upper bound for elements of the array ‘NUMS’.
Explanation:
Time Complexity of the Sieve of Eratosthenes is the worst complexity here, which is O(M X (log(log(M)))).
Auxiliary Space: O(M), where ‘M’ is the upper bound for elements of the array ‘NUMS’.
Explanation: The boolean vector isPrime, is of length M.
Key Takeaways
The above blog has covered a critical interview question asked frequently in big MNCs where Data Structures and Algorithms, and math play an essential role. Minimize swaps required to make all prime-indexed elements as prime is a good question related to trees, which enhances your understanding of the arrays and prime numbers together. It also helps us to learn the Sieve of Eratosthenes, which is a very important and useful algorithm.
Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.
Happy Coding!
39+ registered 