1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Intuition
4.
Approach
5.
Program
5.1.
Example
6.
Complexity Analysis
7.
With Sieve of Eratosthenes
8.
Program
8.1.
Example
9.
Complexity Analysis
10.
Key Takeaways
Last Updated: Mar 27, 2024

# Minimize Swaps Required to Make All Prime-indexed Elements as Prime

## Introduction

To crack the interview of our favorite company, different types of data structures and mathematical concepts like prime numbers are very important to cover.

Array is one of the most important and frequently used data structures, which helps us to store similar types of data elements together at contiguous memory locations and prime numbers are natural numbers that are not divisible by any natural number except for one and itself.

Let us learn both of the above topics by solving a problem.

## Problem Statement

An array of size ‘N’ is given. We have to find the minimum number of swaps required to rearrange the array such that all the elements present at the prime indices should also be prime. If it is not possible to attain the required condition with any number of swaps, print “Not possible”.

### Example

Input: N = 4, NUMS[] = {2, 4, 5, 6}

Output: 1

Explanation: As 2nd index contains 4, which is a composite number. So we can swap elements at index 1 and index 2, so the final array NUMS will be:
{4, 2, 5, 6}

Input: N = 3, NUMS[] = {4, 6, 7}

Output: Not Possible

Explanation: As 2nd index contains a composite number, we do not have any other prime number to swap it with. So the rearrangement is not possible.

## 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;
}

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];

int ans = countSwaps(NUMS, N);

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();

int ans = countSwaps(NUMS, N);

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!

Live masterclass