Dada una string S de longitud N , la tarea es encontrar las operaciones mínimas requeridas para hacer que la frecuencia de cada carácter distinto sea primo. La frecuencia de un carácter se puede aumentar o disminuir en 1 en una sola operación.
Ejemplos:
Entrada: S = “abba”
Salida: 0
Explicación: Hay dos caracteres en la string S y la frecuencia de ‘a’ es 2, que es primo. La frecuencia de ‘b’ es 2, que también es un número primo. Por lo tanto, no se requieren operaciones para este caso.Entrada: S = “aaaaaaaaa”
Salida: 2
Explicación: La frecuencia de ‘a’ en la string es 9. Quite 2 a de la string o agregue 2 a en la string para hacer que la frecuencia de ‘a’ sea prima. Por lo tanto, el número mínimo de operaciones necesarias es 2.
Enfoque ingenuo:
encuentre la frecuencia de cada carácter en la string . Sea la frecuencia X. Encuentra el número primo mayor que X y menor que X. Compara la diferencia entre X y los dos números primos encontrados y elige el número primo más cercano. Sume la diferencia entre el número primo más cercano y X al número de operaciones. Así, se obtendrá el mínimo número de operaciones. Es un enfoque ineficiente ya que no se conocen los límites inferior y superior para encontrar el número primo.
Enfoque eficiente:
- Utilice el algoritmo tamiz para encontrar todos los números primos hasta N y almacenarlos en una array.
- Encuentra el número primo inferior más cercano para todos los números de i = 1 a N y almacena la diferencia entre i y su número primo inferior más cercano en una array, digamos arr1[] .
- Encuentra el número primo más alto más cercano para todos los números de i = 1 a N y almacena la diferencia entre i y su número primo más alto más cercano en una array, digamos arr2[] .
- Recorra la string y encuentre la frecuencia de todos los caracteres distintos en la string y use un mapa_desordenado para guardar las frecuencias de estos caracteres distintos.
- Sea X la frecuencia de cualquier carácter distinto, luego averigüe la distancia entre X y el número primo más cercano de las arrays arr1[] y arr2[] .
- Elija la distancia que sea menor entre los dos y agregue esta distancia al número de operaciones.
- Haga esto para todos los caracteres distintos e imprima el número de operaciones finalmente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
// using the sieve to find
// the prime factors.
void spf_array(int spf[], int d)
{
spf[1] = 1;
int i = 0;
// setting every number
// as prime number initially
for (i = 2; i <= d; i++) {
spf[i] = i;
}
// removing the even numbers as
// they cannot be prime except 2
for (i = 2; i <= d; i = i + 2) {
spf[i] = 2;
}
for (i = 3; i * i <= d; i++) {
// if they are prime
if (spf[i] == i) {
int j;
// iterating the loop for
// prime and eliminate all
// the multiples of three
for (j = i * i; j <= d; j = j + i) {
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
}
// function to find the closest
// prime number of every
// number upto N (size of the string)
void closest_prime_spf(int spf[],
int cspf[], int d)
{
// for the base case
cspf[1] = 1;
int i = 0, j = 0, k = 0;
// iterating to find the
// distance from the
// lesser nearest prime
for (i = 2; i < d; i++) {
if (spf[i] != i) {
cspf[i] = abs(i - k);
}
else {
cspf[i] = -1;
k = i;
}
}
// iterating to find the
// distance from the
// lesser nearest prime
for (i = d - 1; i >= 2; i--) {
if (spf[i] != i) {
if (cspf[i] > abs(k - i)) {
cspf[i] = abs(k - i);
}
}
else {
k = i;
}
}
}
// function to find the
// minimum operation
int minimum_operation(int cspf[],
string s)
{
// created map to find the
// frequency of distinct characters
unordered_map<char, int> m;
// variable to iterate and
// holding the minimum operation
int i = 0, k = 0;
// loop for calculation frequency
for (i = 0; i < s.length(); i++) {
m[s[i]] = m[s[i]] + 1;
}
// iterate over frequency
// if we not get a character
// frequency prime
// then we find the closest
// prime and add
for (auto x : m) {
int h = x.second;
if (cspf[h] != -1) {
k = k + cspf[h];
}
}
return k;
}
// Function to find the
// minimum number of operations
void minOper(string s)
{
int spf[s.length() + 1];
int cspf[s.length() + 1];
// function called to create
// the spf
spf_array(spf, s.length() + 1);
// function called to
// create the cspf
closest_prime_spf(spf, cspf,
s.length() + 1);
cout << minimum_operation(cspf, s)
<< endl;
}
// Driver Code
int main()
{
// input string
string s = "aaaaaaaaabbcccccc";
minOper(s);
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG{
// Using the sieve to find
// the prime factors.
static void spf_array(int spf[], int d)
{
spf[1] = 1;
int i = 0;
// Setting every number
// as prime number initially
for(i = 2; i < d; i++)
{
spf[i] = i;
}
// Removing the even numbers as
// they cannot be prime except 2
for(i = 2; i < d; i = i + 2)
{
spf[i] = 2;
}
for(i = 3; i * i <= d; i++)
{
// If they are prime
if (spf[i] == i)
{
int j;
// Iterating the loop for
// prime and eliminate all
// the multiples of three
for(j = i * i; j < d; j = j + i)
{
if (spf[j] == j)
{
spf[j] = i;
}
}
}
}
}
// Function to find the closest
// prime number of every
// number upto N (size of the String)
static void closest_prime_spf(int spf[],
int cspf[],
int d)
{
// For the base case
cspf[1] = 1;
int i = 0, k = 0;
// Iterating to find the
// distance from the
// lesser nearest prime
for(i = 2; i < d; i++)
{
if (spf[i] != i)
{
cspf[i] = Math.abs(i - k);
}
else
{
cspf[i] = -1;
k = i;
}
}
// Iterating to find the
// distance from the
// lesser nearest prime
for(i = d - 1; i >= 2; i--)
{
if (spf[i] != i)
{
if (cspf[i] > Math.abs(k - i))
{
cspf[i] = Math.abs(k - i);
}
}
else
{
k = i;
}
}
}
// Function to find the
// minimum operation
static int minimum_operation(int cspf[],
String s)
{
// Created map to find the
// frequency of distinct characters
HashMap<Character, Integer> m = new HashMap<>();
// Variable to iterate and
// holding the minimum operation
int i = 0, k = 0;
// Loop for calculation frequency
for(i = 0; i < s.length(); i++)
{
if (m.containsKey(s.charAt(i)))
m.put(s.charAt(i),
m.get(s.charAt(i)) + 1);
else
m.put(s.charAt(i), 1);
}
// Iterate over frequency
// if we not get a character
// frequency prime then we
// find the closest
// prime and add
for(Map.Entry<Character,
Integer> x : m.entrySet())
{
int h = x.getValue();
if (cspf[h] != -1)
{
k = k + cspf[h];
}
}
return k;
}
// Function to find the
// minimum number of operations
static void minOper(String s)
{
int []spf = new int[s.length() + 1];
int []cspf = new int[s.length() + 1];
// Function called to create
// the spf
spf_array(spf, s.length() + 1);
// Function called to
// create the cspf
closest_prime_spf(spf, cspf,
s.length() + 1);
System.out.print(minimum_operation(cspf, s) + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Input String
String s = "aaaaaaaaabbcccccc";
minOper(s);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 code for the above approach from collections import defaultdict # Using the sieve to find # the prime factors. def spf_array(spf, d): spf[1] = 1 i = 0 # Setting every number as prime # number initially and remove # even numbers as 2 as they # cannot be prime except 2 for i in range(2, d + 1): if (i % 2 == 0): spf[i] = 2 else: spf[i] = i i = 3 while i * i <= d: # If they are prime if (spf[i] == i): # Iterating the loop for # prime and eliminate all # the multiples of three j = i * i while j < d + 1: if (spf[j] == j): spf[j] = i j = j + i i += 1 # Function to find the closest # prime number of every number # upto N (size of the string) def closest_prime_spf(spf, cspf, d): # For the base case cspf[1] = 1 i = 0 j = 0 k = 0 # Iterating to find the # distance from the # lesser nearest prime for i in range(2, d): if (spf[i] != i): cspf[i] = abs(i - k) else: cspf[i] = -1 k = i # Iterating to find the # distance from the # lesser nearest prime for i in range(d - 1, 1, -1): if (spf[i] != i): if (cspf[i] > abs(k - i)): cspf[i] = abs(k - i) else: k = i # Function to find the # minimum operation def minimum_operation(cspf, s): # Created map to find the # frequency of distinct characters m = defaultdict(int) # Variable to iterate and # holding the minimum operation i = 0 k = 0 # Loop for calculation frequency for i in range(len(s)): m[s[i]] = m[s[i]] + 1 # Iterate over frequency if we # not get a character frequency # prime then we find the closest # prime and add #print (cspf) for x in m.values(): h = x if (cspf[h] != -1): k = k + cspf[h] return k # Function to find the # minimum number of operations def minOper(s): spf = [0] * (len(s) + 2) cspf = [0] * (len(s) + 2) # Function called to create # the spf spf_array(spf, len(s) + 1) # Function called to # create the cspf closest_prime_spf(spf, cspf, len(s) + 1) print(minimum_operation(cspf, s)) # Driver Code if __name__ == "__main__": # Input string s = "aaaaaaaaabbcccccc" minOper(s) # This code is contributed by chitranayal
C#
// C# code for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Using the sieve to find
// the prime factors.
static void spf_array(int []spf,
int d)
{
spf[1] = 1;
int i = 0;
// Setting every number
// as prime number initially
for(i = 2; i < d; i++)
{
spf[i] = i;
}
// Removing the even numbers as
// they cannot be prime except 2
for(i = 2; i < d; i = i + 2)
{
spf[i] = 2;
}
for(i = 3; i * i <= d; i++)
{
// If they are prime
if (spf[i] == i)
{
int j;
// Iterating the loop for
// prime and eliminate all
// the multiples of three
for(j = i * i; j < d; j = j + i)
{
if (spf[j] == j)
{
spf[j] = i;
}
}
}
}
}
// Function to find the closest
// prime number of every
// number upto N (size of the String)
static void closest_prime_spf(int []spf,
int []cspf,
int d)
{
// For the base case
cspf[1] = 1;
int i = 0, k = 0;
// Iterating to find the
// distance from the
// lesser nearest prime
for(i = 2; i < d; i++)
{
if (spf[i] != i)
{
cspf[i] = Math.Abs(i - k);
}
else
{
cspf[i] = -1;
k = i;
}
}
// Iterating to find the
// distance from the
// lesser nearest prime
for(i = d - 1; i >= 2; i--)
{
if (spf[i] != i)
{
if (cspf[i] > Math.Abs(k - i))
{
cspf[i] = Math.Abs(k - i);
}
}
else
{
k = i;
}
}
}
// Function to find the
// minimum operation
static int minimum_operation(int []cspf,
String s)
{
// Created map to find the
// frequency of distinct characters
Dictionary<char,
int> m = new Dictionary<char,
int>();
// Variable to iterate and
// holding the minimum operation
int i = 0, k = 0;
// Loop for calculation
// frequency
for(i = 0; i < s.Length; i++)
{
if (m.ContainsKey(s[i]))
m[s[i]] = m[s[i]] + 1;
else
m.Add(s[i], 1);
}
// Iterate over frequency
// if we not get a character
// frequency prime then we
// find the closest
// prime and add
foreach(KeyValuePair<char,
int> x in m)
{
int h = x.Value;
if (cspf[h] != -1)
{
k = k + cspf[h];
}
}
return k;
}
// Function to find the
// minimum number of operations
static void minOper(String s)
{
int []spf = new int[s.Length + 1];
int []cspf = new int[s.Length + 1];
// Function called to create
// the spf
spf_array(spf, s.Length + 1);
// Function called to
// create the cspf
closest_prime_spf(spf, cspf,
s.Length + 1);
Console.Write(minimum_operation(
cspf, s) + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Input String
String s = "aaaaaaaaabbcccccc";
minOper(s);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the
// above approach
// Using the sieve to find
// the prime factors.
function spf_array(spf, d) {
spf[1] = 1;
var i = 0;
// Setting every number
// as prime number initially
for (i = 2; i < d; i++) {
spf[i] = i;
}
// Removing the even numbers as
// they cannot be prime except 2
for (i = 2; i < d; i = i + 2) {
spf[i] = 2;
}
for (i = 3; i * i <= d; i++) {
// If they are prime
if (spf[i] === i) {
var j;
// Iterating the loop for
// prime and eliminate all
// the multiples of three
for (j = i * i; j < d; j = j + i) {
if (spf[j] === j) {
spf[j] = i;
}
}
}
}
}
// Function to find the closest
// prime number of every
// number upto N (size of the String)
function closest_prime_spf(spf, cspf, d) {
// For the base case
cspf[1] = 1;
var i = 0,
k = 0;
// Iterating to find the
// distance from the
// lesser nearest prime
for (i = 2; i < d; i++) {
if (spf[i] !== i) {
cspf[i] = Math.abs(i - k);
} else {
cspf[i] = -1;
k = i;
}
}
// Iterating to find the
// distance from the
// lesser nearest prime
for (i = d - 1; i >= 2; i--) {
if (spf[i] !== i) {
if (cspf[i] > Math.abs(k - i)) {
cspf[i] = Math.abs(k - i);
}
} else {
k = i;
}
}
}
// Function to find the
// minimum operation
function minimum_operation(cspf, s) {
// Created map to find the
// frequency of distinct characters
var m = {};
// Variable to iterate and
// holding the minimum operation
var i = 0,
k = 0;
// Loop for calculation
// frequency
for (i = 0; i < s.length; i++) {
if (m.hasOwnProperty(s[i])) m[s[i]] = m[s[i]] + 1;
else m[s[i]] = 1;
}
// Iterate over frequency
// if we not get a character
// frequency prime then we
// find the closest
// prime and add
for (const [key, value] of Object.entries(m)) {
var h = value;
if (cspf[h] !== -1) {
k = k + cspf[h];
}
}
return k;
}
// Function to find the
// minimum number of operations
function minOper(s) {
var spf = new Array(s.length + 1).fill(0);
var cspf = new Array(s.length + 1).fill(0);
// Function called to create
// the spf
spf_array(spf, s.length + 1);
// Function called to
// create the cspf
closest_prime_spf(spf, cspf, s.length + 1);
document.write(minimum_operation(cspf, s) + "<br>");
}
// Driver Code
// Input String
var s = "aaaaaaaaabbcccccc";
minOper(s);
</script>
Producción:
3
Complejidad de tiempo: O(N * log(log(N)))
Complejidad de espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vabzcode12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA