Dado un entero positivo N , la tarea es encontrar el número mínimo de operaciones requeridas para reducir N a 1 dividiendo repetidamente N entre sus divisores propios o disminuyendo N en 1 .
Ejemplos:
Entrada: N = 9
Salida: 3
Explicación:
Los divisores propios de N(= 9) son {1, 3}. Se realizan las siguientes operaciones para reducir N a 1:
Operación 1: Dividir N(= 9) entre 3 (que es un divisor propio de N(= 9) modifica el valor de N a 9/3 = 1.
Operación 2: Decrementar el el valor de N(= 3) en 1 modifica el valor de N a 3 – 1 = 2.
Operación 3: Decrementar el valor de N(= 2) en 1 modifica el valor de N a 2 – 1 = 1.
Por lo tanto, el el número total de operaciones requeridas es 3.Entrada: N = 4
Salida: 2
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Si el valor de N es par, entonces se puede reducir al valor 2 dividiendo N por N / 2 seguido de una disminución de 2 a 1 . Por lo tanto, el número mínimo de pasos necesarios es 2 .
- De lo contrario, el valor de N se puede igualar al disminuirlo y se puede reducir a 1 usando los pasos anteriores.
Siga los pasos que se indican a continuación para resolver el problema.
- Inicialice una variable, digamos cnt como 0 , para almacenar el número mínimo de pasos necesarios para reducir N a 1 .
- Itere un ciclo hasta que N se reduzca a 1 y realice los siguientes pasos:
- Si el valor de N es igual a 2 o N es impar , actualice el valor de N = N – 1 e incremente cnt en 1 .
- De lo contrario, actualice el valor de N = N / (N / 2) e incremente cnt en 1.
- Después de completar los pasos anteriores, imprima el valor de cnt como resultado.
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 reduce N to 1
int reduceToOne(long long int N)
{
// Stores the number
// of steps required
int cnt = 0;
while (N != 1) {
// If the value of N
// is equal to 2 or N is odd
if (N == 2 or (N % 2 == 1)) {
// Decrement N by 1
N = N - 1;
// Increment cnt by 1
cnt++;
}
// If N is even
else if (N % 2 == 0) {
// Update N
N = N / (N / 2);
// Increment cnt by 1
cnt++;
}
}
// Return the number
// of steps obtained
return cnt;
}
// Driver Code
int main()
{
long long int N = 35;
cout << reduceToOne(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 reduce N to 1
static int reduceToOne(long N)
{
// Stores the number
// of steps required
int cnt = 0;
while (N != 1)
{
// If the value of N
// is equal to 2 or N is odd
if (N == 2 || (N % 2 == 1))
{
// Decrement N by 1
N = N - 1;
// Increment cnt by 1
cnt++;
}
// If N is even
else if (N % 2 == 0)
{
// Update N
N = N / (N / 2);
// Increment cnt by 1
cnt++;
}
}
// Return the number
// of steps obtained
return cnt;
}
// Driver Code
public static void main(String[] args)
{
long N = 35;
System.out.println(reduceToOne(N));
}
}
// This code is contributed by Dharanendra L V.
Python3
# python program for the above approach # Function to find the minimum number # of steps required to reduce N to 1 def reduceToOne(N): # Stores the number # of steps required cnt = 0 while (N != 1): # If the value of N # is equal to 2 or N is odd if (N == 2 or (N % 2 == 1)): # Decrement N by 1 N = N - 1 # Increment cnt by 1 cnt += 1 # If N is even elif (N % 2 == 0): # Update N N = N / (N / 2) # Increment cnt by 1 cnt += 1 # Return the number # of steps obtained return cnt # Driver Code if __name__ == '__main__': N = 35 print (reduceToOne(N)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the minimum number
// of steps required to reduce N to 1
static int reduceToOne(long N)
{
// Stores the number
// of steps required
int cnt = 0;
while (N != 1)
{
// If the value of N
// is equal to 2 or N is odd
if (N == 2 || (N % 2 == 1))
{
// Decrement N by 1
N = N - 1;
// Increment cnt by 1
cnt++;
}
// If N is even
else if (N % 2 == 0)
{
// Update N
N = N / (N / 2);
// Increment cnt by 1
cnt++;
}
}
// Return the number
// of steps obtained
return cnt;
}
// Driver Code
public static void Main()
{
long N = 35;
Console.WriteLine(reduceToOne(N));
}
}
// This code s contributed by code_hunt.
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// of steps required to reduce N to 1
function reduceToOne( N)
{
// Stores the number
// of steps required
let cnt = 0;
while (N != 1) {
// If the value of N
// is equal to 2 or N is odd
if (N == 2 || (N % 2 == 1)) {
// Decrement N by 1
N = N - 1;
// Increment cnt by 1
cnt++;
}
// If N is even
else if (N % 2 == 0) {
// Update N
N = Math.floor(N / Math.floor(N / 2));
// Increment cnt by 1
cnt++;
}
}
// Return the number
// of steps obtained
return cnt;
}
// Driver Code
let N = 35;
document.write(reduceToOne(N));
// This code is contributed by jana_sayantan.
</script>
3
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitmanathiya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA