Minimum changes required to make all Array elements Prime
Given an array of integers arr[], the task is to count the minimum number of changes required to convert each array element to its nearest prime.
Examples:
Input: arr[] = {4, 25, 13, 6, 20}
Output: 5
Explanation:
- 1 increment required to convert 4 to its nearest prime 5.
- 2 decrements required to convert 25 to its nearest prime 23.
- 13 itself is a prime.
- 1 increment required to convert 6 to its nearest prime 7.
- 1 decrement required to convert 20 to its nearest prime 19.
Hence, required number of changes = 1 + 2 + 0 + 1 + 1 = 5
Input: arr[] = {1, 2, 9}
Output: 3
Explanation:
- 1 increment required to convert 1 to its nearest prime 2.
- 2 itself is a prime.
- 2 increments required to convert 9 to its nearest prime 11.
Hence, required number of changes = 1 + 0 + 2 = 3
Naive Approach:
Traverse the array and for every array element, find its nearest prime number to its right starting from arr[i] + 1 and to its left starting from arr[i] – 1. Once computed, calculate their difference from arr[i] and consider the smaller difference. The Sum of all such differences gives the desired output.
Time Complexity: O(N * maxi2), where maxi denotes the maximum element in the array.
Efficient Approach:
This problem can be solved using Sieve of Eratosthenes. Follow the steps below to solve the problem:
- Find the maximum element from the given array.
- Let maxi be the maximum element present on the array. Generate all prime numbers in the range [1, 2*maxi] and store them.
- Traverse the array and find the index of the next greater prime number for every array element using lower_bound, say x.
- Calculate the absolute difference between arr[i] and primes[x] and between arr[i] and primes[x – 1].
- Add the minimum of the two to ans.
- After complete traversal of the array, print the final value of ans as the answer.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to generate all primes vector< int > SieveOfEratosthenes( int n) { bool prime[2 * n + 1]; memset (prime, true , sizeof (prime)); for ( int p = 2; p * p <= 2 * n; p++) { // If p is a prime if (prime[p] == true ) { // Mark all its multiples // as non-prime for ( int i = p * p; i <= 2 * n; i += p) prime[i] = false ; } } vector< int > primes; // Store all prime numbers for ( int p = 2; p <= 2 * n; p++) if (prime[p]) primes.push_back(p); // Return the list of primes return primes; } // Function to calculate the // minimum increments to // convert every array elements // to a prime int minChanges(vector< int > arr) { int n = arr.size(); int ans = 0; // Extract maximum element // of the given array int maxi = *max_element(arr.begin(), arr.end()); vector< int > primes = SieveOfEratosthenes(maxi); for ( int i = 0; i < n; i++) { // Extract the index which has // the next greater prime int x = lower_bound(primes.begin(), primes.end(), arr[i]) - primes.begin(); // Store the difference // between the prime and // the array element int minm = abs (primes[x] - arr[i]); if (x > 1) { minm = min(minm, abs (primes[x - 1] - arr[i])); } ans += minm; } return ans; } // Driver Code int main() { vector< int > arr = { 4, 25, 13, 6, 20 }; cout << minChanges(arr); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; import java.lang.*; class GFG{ // Function to generate all primes static ArrayList<Integer> SieveOfEratosthenes( int n) { boolean [] prime = new boolean [ 2 * n + 1 ]; Arrays.fill(prime, true ); for ( int p = 2 ; p * p <= 2 * n; p++) { // If p is a prime if (prime[p] == true ) { // Mark all its multiples // as non-prime for ( int i = p * p; i <= 2 * n; i += p) prime[i] = false ; } } ArrayList<Integer> primes = new ArrayList<>(); // Store all prime numbers for ( int p = 2 ; p <= 2 * n; p++) if (prime[p]) primes.add(p); // Return the list of primes return primes; } // Function to calculate the // minimum increments to // convert every array elements // to a prime static int minChanges( int [] arr) { int n = arr.length; int ans = 0 ; // Extract maximum element // of the given array int maxi = arr[ 0 ]; for ( int i = 1 ; i < arr.length; i++) maxi = Math.max(maxi, arr[i]); ArrayList<Integer> primes = SieveOfEratosthenes(maxi); for ( int i = 0 ; i < n; i++) { // Extract the index which has // the next greater prime int x = - 1 ; for ( int j = 0 ; j < primes.size(); j++) { if (arr[i] == primes.get(j)) { x = j; break ; } else if (arr[i] < primes.get(j)) { x = j; break ; } } // Store the difference // between the prime and // the array element int minm = Math.abs(primes.get(x) - arr[i]); if (x > 1 ) { minm = Math.min(minm, Math.abs(primes.get(x - 1 ) - arr[i])); } ans += minm; } return ans; } // Driver code public static void main (String[] args) { int [] arr = { 4 , 25 , 13 , 6 , 20 }; System.out.println(minChanges(arr)); } } // This code is contributed by offbeat |
Python3
# Python program to implement # the above approach # Function to generate all primes def SieveOfEratosthenes(n): prime = [ True for i in range ( 2 * n + 1 )] p = 2 while (p * p < = 2 * n): # If p is a prime if (prime[p] = = True ): # Mark all its multiples # as non-prime i = p * p while (i < = n * 2 ): prime[i] = False i + = p p + = 1 primes = [] # Store all prime numbers for p in range ( 2 , ( 2 * n) + 1 ): if (prime[p]): primes.append(p) # Return the list of primes return primes # Function to calculate the # minimum increments to # convert every array elements # to a prime def minChanges(arr): n = len (arr) ans = 0 # Extract maximum element # of the given array maxi = max (arr) primes = SieveOfEratosthenes(maxi) for i in range (n): # Extract the index which has # the next greater prime x = - 1 for j in range ( len (primes)): if (arr[i] = = primes[j]): x = j break elif (arr[i] < primes[j]): x = j break # Store the difference # between the prime and # the array element minm = abs (primes[x] - arr[i]) if (x > 1 ): minm = min (minm, abs (primes[x - 1 ] - arr[i])) ans + = minm return ans # Driver code arr = [ 4 , 25 , 13 , 6 , 20 ] print (minChanges(arr)) # This code is contributed by avanitrachhadiya2155 |
C#
// C# program to implement // the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to generate all primes static List< int > SieveOfEratosthenes( int n) { bool [] prime = new bool [2 * n + 1]; Array.Fill(prime, true ); for ( int p = 2; p * p <= 2 * n; p++) { // If p is a prime if (prime[p] == true ) { // Mark all its multiples // as non-prime for ( int i = p * p; i <= 2 * n; i += p) prime[i] = false ; } } List< int > primes = new List< int >(); // Store all prime numbers for ( int p = 2; p <= 2 * n; p++) if (prime[p]) primes.Add(p); // Return the list of primes return primes; } // Function to calculate the // minimum increments to // convert every array elements // to a prime static int minChanges( int [] arr) { int n = arr.Length; int ans = 0; // Extract maximum element // of the given array int maxi = arr[0]; for ( int i = 1; i < arr.Length; i++) maxi = Math.Max(maxi, arr[i]); List< int > primes = SieveOfEratosthenes(maxi); for ( int i = 0; i < n; i++) { // Extract the index which has // the next greater prime int x = -1; for ( int j = 0; j < primes.Count; j++) { if (arr[i] == primes[j]) { x = j; break ; } else if (arr[i] < primes[j]) { x = j; break ; } } // Store the difference // between the prime and // the array element int minm = Math.Abs(primes[x]- arr[i]); if (x > 1) { minm = Math.Min(minm, Math.Abs(primes[x - 1] - arr[i])); } ans += minm; } return ans; } // Driver code public static void Main( string [] args) { int [] arr = { 4, 25, 13, 6, 20 }; Console.Write(minChanges(arr)); } } // This code is contributed by rutvik_56. |
Javascript
<script> // Javascript Program to implement // the above approach // Function to generate all primes function SieveOfEratosthenes(n) { let prime = new Array(2 * n + 1); prime.fill( true ) for (let p = 2; p * p <= 2 * n; p++) { // If p is a prime if (prime[p] == true ) { // Mark all its multiples // as non-prime for (let i = p * p; i <= 2 * n; i += p) prime[i] = false ; } } let primes = new Array(); // Store all prime numbers for (let p = 2; p <= 2 * n; p++) if (prime[p]) primes.push(p); // Return the list of primes return primes; } // Function to calculate the // minimum increments to // convert every array elements // to a prime function minChanges(arr) { let n = arr.length; let ans = 0; // Extract maximum element // of the given array let maxi = arr.sort((a, b) => b - a)[0]; let primes = SieveOfEratosthenes(maxi); for (let i = 0; i < n; i++) { // Extract the index which has // the next greater prime let x = -1 for (let j = 0; j < primes.length; j++){ if (arr[i] == primes[j]){ x = j break } else if (arr[i] < primes[j]){ x = j break } } // Store the difference // between the prime and // the array element let minm = Math.abs(primes[x] - arr[i]); if (x > 1) { minm = Math.min(minm, Math.abs(primes[x - 1] - arr[i])); } ans += minm; } return ans; } // Driver Code let arr = [ 4, 25, 13, 6, 20 ]; document.write(minChanges(arr)); // This code is contributed by _saurabh_jaiswal </script> |
5
Time Complexity: O(log(log(N)) + O(NlogN)
Auxiliary Space: O(N)