Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el número mínimo de números primos necesarios para restar de los elementos de la array para hacer que todos los elementos de la array sean iguales.
Ejemplos:
Entrada: arr[]= {7, 10, 4, 5}
Salida: 5
Explicación: La siguiente resta de números primos hace que todos los elementos de la array sean iguales:
- Restar 5 de arr[0] modifica arr[] a {2, 10, 4, 5}.
- Restar 5 de arr[1] modifica arr[] a {2, 5, 4, 5}.
- Restar 3 de arr[1] modifica arr[] a {2, 2, 4, 5}.
- Restar 2 de arr[2] modifica arr[] a {2, 2, 2, 5}.
- Restar 3 de arr[3] modifica arr[] a {2, 2, 2, 2}.
Por lo tanto, el número total de operaciones requeridas es 5.
Entrada: arr[]= {10, 17, 37, 43, 50}
Salida: 8
Enfoque: El problema dado se puede resolver usando las siguientes observaciones:
- Todo número par mayor que 2 es la suma de dos números primos .
- Todo número impar mayor que 1 , se puede representar como la suma de como máximo 3 números primos . A continuación se muestran los posibles casos para el mismo:
- Caso 1: Si N es primo.
- Caso 2: Si (N – 2) es primo. Por lo tanto, se requieren 2 números, es decir, 2 y N – 2 .
- Caso 3: Si (N – 3) es par, entonces usando la conjetura de Goldbach . (N – 3) se puede representar como la suma de dos números primos.
- Por lo tanto, la idea es reducir cada elemento de la array al valor mínimo de la array (por ejemplo, M ) arr[] y si existe un elemento en la array que tenga un valor (M + 1) , entonces reduzca cada elemento al valor (M – 2) .
Siga los pasos a continuación para resolver este problema:
- Inicialice una array, digamos prime[] , de tamaño 10 5 , para almacenar en cada índice i th , ya sea que i sea un número primo o no use Sieve Of Eratosthenes .
- Encuentre el elemento mínimo presente en la array , digamos M.
- Si existe algún elemento en la array arr[] con valor (M + 1) , actualice M a (M – 2) .
- Inicialice una variable, digamos count , para almacenar la cantidad de operaciones requeridas para hacer que todos los elementos de la array sean iguales.
- Recorra la array dada arr[] y realice los siguientes pasos:
- Encuentre la diferencia entre arr[i] y M , digamos D .
- Actualice el valor de count de acuerdo con los siguientes valores de D :
- Si el valor de D es un número primo , incremente la cuenta en 1 .
- Si el valor de D es un número par , incremente la cuenta en 2 .
- Si el valor de D es un número impar , y si (D – 2) es un número primo, entonces incremente la cuenta en 2 . De lo contrario, incremente el conteo en 3 .
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define limit 100000
using namespace std;
// Stores the sieve of prime numbers
bool prime[limit + 1];
// Function that performs the Sieve of
// Eratosthenes
void sieve()
{
// Initialize all numbers as prime
memset(prime, true, sizeof(prime));
// Iterate over the range [2, 1000]
for (int p = 2; p * p <= limit; p++) {
// If the current element
// is a prime number
if (prime[p] == true) {
// Mark all its multiples as false
for (int i = p * p; i <= limit; i += p)
prime[i] = false;
}
}
}
// Function to find the minimum number of
// subtraction of primes numbers required
// to make all array elements the same
int findOperations(int arr[], int n)
{
// Perform sieve of eratosthenes
sieve();
int minm = INT_MAX;
// Find the minimum value
for (int i = 0; i < n; i++) {
minm = min(minm, arr[i]);
}
// Stores the value to each array
// element should be reduced
int val = minm;
for (int i = 0; i < n; i++) {
// If an element exists with
// value (M + 1)
if (arr[i] == minm + 1) {
val = minm - 2;
break;
}
}
// Stores the minimum count of
// subtraction of prime numbers
int cnt = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
int D = arr[i] - val;
// If D is equal to 0
if (D == 0) {
continue;
}
// If D is a prime number
else if (prime[D] == true) {
// Increase count by 1
cnt += 1;
}
// If D is an even number
else if (D % 2 == 0) {
// Increase count by 2
cnt += 2;
}
else {
// If D - 2 is prime
if (prime[D - 2] == true) {
// Increase count by 2
cnt += 2;
}
// Otherwise, increase
// count by 3
else {
cnt += 3;
}
}
}
return cnt;
}
// Driver Code
int main()
{
int arr[] = { 7, 10, 4, 5 };
int N = 4;
cout << findOperations(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
static int limit = 100000;
// Stores the sieve of prime numbers
static boolean prime[];
// Function that performs the Sieve of
// Eratosthenes
static void sieve()
{
prime = new boolean[limit + 1];
// Initialize all numbers as prime
Arrays.fill(prime, true);
// Iterate over the range [2, 1000]
for(int p = 2; p * p <= limit; p++)
{
// If the current element
// is a prime number
if (prime[p] == true)
{
// Mark all its multiples as false
for(int i = p * p; i <= limit; i += p)
prime[i] = false;
}
}
}
// Function to find the minimum number of
// subtraction of primes numbers required
// to make all array elements the same
static int findOperations(int arr[], int n)
{
// Perform sieve of eratosthenes
sieve();
int minm = Integer.MAX_VALUE;
// Find the minimum value
for(int i = 0; i < n; i++)
{
minm = Math.min(minm, arr[i]);
}
// Stores the value to each array
// element should be reduced
int val = minm;
for(int i = 0; i < n; i++)
{
// If an element exists with
// value (M + 1)
if (arr[i] == minm + 1)
{
val = minm - 2;
break;
}
}
// Stores the minimum count of
// subtraction of prime numbers
int cnt = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
int D = arr[i] - val;
// If D is equal to 0
if (D == 0)
{
continue;
}
// If D is a prime number
else if (prime[D] == true)
{
// Increase count by 1
cnt += 1;
}
// If D is an even number
else if (D % 2 == 0)
{
// Increase count by 2
cnt += 2;
}
else
{
// If D - 2 is prime
if (prime[D - 2] == true)
{
// Increase count by 2
cnt += 2;
}
// Otherwise, increase
// count by 3
else
{
cnt += 3;
}
}
}
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 7, 10, 4, 5 };
int N = 4;
System.out.println(findOperations(arr, N));
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach import sys limit = 100000 # Stores the sieve of prime numbers prime = [True] * (limit + 1) # Function that performs the Sieve of # Eratosthenes def sieve(): # Iterate over the range [2, 1000] p = 2 while(p * p <= limit): # If the current element # is a prime number if (prime[p] == True): # Mark all its multiples as false for i in range(p * p, limit, p): prime[i] = False p += 1 # Function to find the minimum number of # subtraction of primes numbers required # to make all array elements the same def findOperations(arr, n): # Perform sieve of eratosthenes sieve() minm = sys.maxsize # Find the minimum value for i in range(n): minm = min(minm, arr[i]) # Stores the value to each array # element should be reduced val = minm for i in range(n): # If an element exists with # value (M + 1) if (arr[i] == minm + 1): val = minm - 2 break # Stores the minimum count of # subtraction of prime numbers cnt = 0 # Traverse the array for i in range(n): D = arr[i] - val # If D is equal to 0 if (D == 0): continue # If D is a prime number elif (prime[D] == True): # Increase count by 1 cnt += 1 # If D is an even number elif (D % 2 == 0): # Increase count by 2 cnt += 2 else: # If D - 2 is prime if (prime[D - 2] == True): # Increase count by 2 cnt += 2 # Otherwise, increase # count by 3 else: cnt += 3 return cnt # Driver Code arr = [ 7, 10, 4, 5 ] N = 4 print(findOperations(arr, N)) # This code is contributed by splevel62
C#
// C# program for the above approach
using System;
class GFG{
static int limit = 100000;
// Stores the sieve of prime numbers
static bool[] prime;
// Function that performs the Sieve of
// Eratosthenes
static void sieve()
{
prime = new bool[limit + 1];
// Initialize all numbers as prime
Array.Fill(prime, true);
// Iterate over the range [2, 1000]
for(int p = 2; p * p <= limit; p++)
{
// If the current element
// is a prime number
if (prime[p] == true)
{
// Mark all its multiples as false
for(int i = p * p; i <= limit; i += p)
prime[i] = false;
}
}
}
// Function to find the minimum number of
// subtraction of primes numbers required
// to make all array elements the same
static int findOperations(int[] arr, int n)
{
// Perform sieve of eratosthenes
sieve();
int minm = Int32.MaxValue;
// Find the minimum value
for(int i = 0; i < n; i++)
{
minm = Math.Min(minm, arr[i]);
}
// Stores the value to each array
// element should be reduced
int val = minm;
for(int i = 0; i < n; i++)
{
// If an element exists with
// value (M + 1)
if (arr[i] == minm + 1)
{
val = minm - 2;
break;
}
}
// Stores the minimum count of
// subtraction of prime numbers
int cnt = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
int D = arr[i] - val;
// If D is equal to 0
if (D == 0)
{
continue;
}
// If D is a prime number
else if (prime[D] == true)
{
// Increase count by 1
cnt += 1;
}
// If D is an even number
else if (D % 2 == 0)
{
// Increase count by 2
cnt += 2;
}
else
{
// If D - 2 is prime
if (prime[D - 2] == true)
{
// Increase count by 2
cnt += 2;
}
// Otherwise, increase
// count by 3
else
{
cnt += 3;
}
}
}
return cnt;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 7, 10, 4, 5 };
int N = 4;
Console.WriteLine(findOperations(arr, N));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
var limit = 100000;
// Stores the sieve of prime numbers
var prime = Array(limit + 1).fill(true);
// Function that performs the Sieve of
// Eratosthenes
function sieve()
{
// Iterate over the range [2, 1000]
for (p = 2; p * p <= limit; p++) {
// If the current element
// is a prime number
if (prime[p] == true) {
// Mark all its multiples as false
for (i = p * p; i <= limit; i += p)
prime[i] = false;
}
}
}
// Function to find the minimum number of
// subtraction of primes numbers required
// to make all array elements the same
function findOperations(arr, n)
{
// Perform sieve of eratosthenes
sieve();
var minm = Number.MAX_VALUE;
// Find the minimum value
for (i = 0; i < n; i++) {
minm = Math.min(minm, arr[i]);
}
// Stores the value to each array
// element should be reduced
var val = minm;
for (i = 0; i < n; i++) {
// If an element exists with
// value (M + 1)
if (arr[i] == minm + 1) {
val = minm - 2;
break;
}
}
// Stores the minimum count of
// subtraction of prime numbers
var cnt = 0;
// Traverse the array
for (i = 0; i < n; i++) {
var D = arr[i] - val;
// If D is equal to 0
if (D == 0) {
continue;
}
// If D is a prime number
else if (prime[D] == true) {
// Increase count by 1
cnt += 1;
}
// If D is an even number
else if (D % 2 == 0) {
// Increase count by 2
cnt += 2;
}
else {
// If D - 2 is prime
if (prime[D - 2] == true) {
// Increase count by 2
cnt += 2;
}
// Otherwise, increase
// count by 3
else {
cnt += 3;
}
}
}
return cnt;
}
// Driver Code
var arr = [7, 10, 4, 5];
var N = 4;
document.write(findOperations(arr, N));
</script>
Producción:
5
Complejidad de tiempo: O(N + M * log(log(M))), M es el tamaño del
espacio auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA