Dada una array de enteros arr[] , la tarea es contar el número mínimo de cambios necesarios para convertir cada elemento de la array a su número primo más cercano.
Ejemplos:
Entrada: arr[] = {4, 25, 13, 6, 20}
Salida: 5
Explicación:
- Se requiere 1 incremento para convertir 4 a su 5 primo más cercano.
- Se requieren 2 decrementos para convertir 25 a su primo 23 más cercano.
- 13 en sí mismo es un número primo.
- Se requiere 1 incremento para convertir 6 a su 7 primo más cercano.
- Se requiere 1 decremento para convertir 20 a su primo 19 más cercano.
Por lo tanto, número requerido de cambios = 1 + 2 + 0 + 1 + 1 = 5
Entrada: arr[] = {1, 2, 9}
Salida: 3
Explicación:
- Se requiere 1 incremento para convertir 1 a su primo 2 más cercano.
- 2 en sí mismo es un número primo.
- Se requieren 2 incrementos para convertir 9 a su 11 primo más cercano.
Por lo tanto, número requerido de cambios = 1 + 0 + 2 = 3
Enfoque ingenuo:
recorra la array y, para cada elemento de la array, encuentre su número primo más cercano a su derecha comenzando desde arr[i] + 1 y a su izquierda comenzando desde arr[i] – 1. Una vez calculado, calcule su diferencia desde arr[ i] y considere la diferencia más pequeña. La suma de todas esas diferencias da el resultado deseado.
Complejidad de tiempo: O(N * maxi 2 ), donde maxi denota el elemento máximo en la array.
Enfoque eficiente:
este problema se puede resolver utilizando la criba de Eratóstenes . Siga los pasos a continuación para resolver el problema:
- Encuentre el elemento máximo de la array dada.
- Sea maxi el elemento máximo presente en la array. Genere todos los números primos en el rango [1, 2*maxi] y guárdelos.
- Recorra la array y encuentre el índice del siguiente número primo mayor para cada elemento de la array usando lower_bound , digamos x .
- Calcula la diferencia absoluta entre arr[i] y primos[x] y entre arr[i] y primos[x – 1].
- Sume el mínimo de los dos a ans .
- Después de completar el recorrido de la array, imprima el valor final de ans como respuesta.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
5
Complejidad de tiempo: O(log(log(N)) + O(NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Thirumalaisrinivasan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA