Dado un entero positivo N y una string S , inicialmente es «A» , la tarea es minimizar el número de operaciones requeridas para formar una string que consta de N números de A realizando una de las siguientes operaciones en cada paso:
- Copie todos los caracteres presentes en la string S .
- Agregue todos los caracteres a la string S que se copiaron la última vez.
Ejemplos:
Entrada: N = 3
Salida: 3
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: Copia la string inicial S una vez, es decir, «A».
Operación 2: Agregar la string copiada, es decir, «A», a la string S modifica la string S a «AA».
Operación 3: Agregar la string copiada, es decir, «A», a la string S modifica la string S a «AAA».
Por lo tanto, el número mínimo de operaciones requeridas para obtener 3 A es 3.Entrada: N = 7
Salida: 7
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Si N = P 1 *P 2 *P m donde {P 1 , P 2 , …, P m } son los números primos , entonces uno puede realizar los siguientes movimientos:
- Primero, copie la string y luego péguela (P 1 – 1) veces.
- Del mismo modo, copiando nuevamente la string y pegándola (P 2 – 1) veces.
- Realizando M veces con el número primo restante , se obtendrá la string con N números de A.
- Por lo tanto, el número total de movimientos mínimos necesarios viene dado por (P 1 + P 2 + … + P m ) .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 , que almacene el número resultante de operaciones.
- Encuentre los factores primos y su potencia del entero N dado .
- Ahora, repita todos los factores primos de N e incremente el valor de ans por el producto del factor primo y su potencia.
- Finalmente, después de completar los pasos anteriores, imprima el valor de ans como el número mínimo de movimientos resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of steps required to form N number
// of A's
int minSteps(int N)
{
// Stores the count of steps needed
int ans = 0;
// Traverse over the range [2, N]
for (int d = 2; d * d <= N; d++) {
// Iterate while N is divisible
// by d
while (N % d == 0) {
// Increment the value of
// ans by d
ans += d;
// Divide N by d
N /= d;
}
}
// If N is not 1
if (N != 1) {
ans += N;
}
// Return the ans
return ans;
}
// Driver Code
int main()
{
int N = 3;
cout << minSteps(N);
return 0;
}
Java
// Java Program for the above approach
import java.io.*;
class GFG
{
// Function to find the minimum number
// of steps required to form N number
// of A's
static int minSteps(int N)
{
// Stores the count of steps needed
int ans = 0;
// Traverse over the range [2, N]
for (int d = 2; d * d <= N; d++) {
// Iterate while N is divisible
// by d
while (N % d == 0) {
// Increment the value of
// ans by d
ans += d;
// Divide N by d
N /= d;
}
}
// If N is not 1
if (N != 1) {
ans += N;
}
// Return the ans
return ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
minSteps(N);
System.out.println(minSteps(N));
}
}
// This code is contributed by lokesh potta.
Python3
# Python3 program for the above approach # Function to find the minimum number # of steps required to form N number # of A's def minSteps( N): # Stores the count of steps needed ans = 0 # Traverse over the range [2, N] d = 2 while(d * d <= N): # Iterate while N is divisible # by d while (N % d == 0): # Increment the value of # ans by d ans += d # Divide N by d N /= d d += 1 # If N is not 1 if (N != 1): ans += N # Return the ans return ans # Driver Code N = 3 print(minSteps(N)) # This code is contributed by shivanisinghss2110
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum number
// of steps required to form N number
// of A's
static int minSteps(int N)
{
// Stores the count of steps needed
int ans = 0;
// Traverse over the range [2, N]
for (int d = 2; d * d <= N; d++) {
// Iterate while N is divisible
// by d
while (N % d == 0) {
// Increment the value of
// ans by d
ans += d;
// Divide N by d
N /= d;
}
}
// If N is not 1
if (N != 1) {
ans += N;
}
// Return the ans
return ans;
}
// Driver Code
static public void Main ()
{
int N = 3;
Console.Write(minSteps(N));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript Program for the above approach
// Function to find the minimum number
// of steps required to form N number
// of A's
function minSteps(N)
{
// Stores the count of steps needed
var ans = 0;
// Traverse over the range [2, N]
for (var d = 2; d * d <= N; d++) {
// Iterate while N is divisible
// by d
while (N % d == 0) {
// Increment the value of
// ans by d
ans += d;
// Divide N by d
N /= d;
}
}
// If N is not 1
if (N != 1) {
ans += N;
}
// Return the ans
return ans;
}
// Driver Code
var N = 3;
minSteps(N);
document.write(minSteps(N));
// This code is contributed by shivanisinghss2110
</script>
3
Complejidad de Tiempo: O(√N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por udaykrishnap2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA