Dado un entero positivo N . Encuentre el número mínimo de operaciones necesarias para reducir N a 0 cuando N puede reducirse por su divisor en cada operación.
Ejemplo:
Entrada: N = 5
Salida: 4
Explicación:
Reducir 5 como 5-1=4.
Reduce 4 como 4-2=2.
Reduzca 2 como 2-1=1.
Reducir 1 como 1-1=0.Entrada: N = 8
Salida: 4
Explicación:
Reducir 8 como 8-4=4.
Reduce 4 como 4-2=2.
Reduzca 2 como 2-1=1.
Reducir 1 como 1-1=0.
Enfoque ingenuo:
Un enfoque fácil es encontrar el divisor más alto de N cada vez hasta que N se convierta en 0.
Siga los pasos a continuación para resolver este problema:
- Atraviese hasta que N se convierta en 0 .
- Encuentre el divisor más alto de N y reste de N .
- Cuente el número de iteraciones requeridas para que N se convierta en 0 de esta manera.
- Devuelva el recuento calculado anteriormente como la respuesta final.
C++14
// C++ program to minimize operations // to reduce N to 0 by replacing // N by its divisor at each step #include <bits/stdc++.h> using namespace std; typedef long long ll; ll findElement(ll N) { for (ll i = 2; i * i <= N; i++) { if (N % i == 0) return N / i; } return 1; } // Function to count minimum number // of operation ll minOperations(ll N) { if (N < 0) return -1; ll count = 0; while (N) { ll divisor = findElement(N); N -= divisor; count++; } return count; } // Driver code int main() { ll N = 5; cout << minOperations(N); return 0; }
Java
// Java program to minimize operations // to reduce N to 0 by replacing // N by its divisor at each step import java.io.*; class GFG { static long findElement(long N) { for (long i = 2; i * i <= N; i++) { if (N % i == 0) return N / i; } return 1; } // Function to count minimum number // of operation static long minOperations(long N) { if (N < 0) return -1; long count = 0; while (N > 0) { long divisor = findElement(N); N -= divisor; count++; } return count; } // Driver code public static void main (String[] args) { long N = 5; System.out.print(minOperations(N)); } } // This code is contributed by hrithikgarg03188.
Python3
# Python3 program to minimize operations # to reduce N to 0 by replacing N by its # divisor at each step # function to find the element def findElement(N): i = 2 while i * i <= N: if N % i == 0: return int(N / i) i += 1 return 1 # function to count the min number of operations def minOperations(N): if N < 0: return -1 count = 0 while N: divisor = findElement(N) N -= divisor count += 1 return count # Driver Code N = 5 print(minOperations(N)) # This code is contributed by phasing17
C#
// C# program to minimize operations // to reduce N to 0 by replacing // N by its divisor at each step using System; class GFG { static long findElement(long N) { for (long i = 2; i * i <= N; i++) { if (N % i == 0) return N / i; } return 1; } // Function to count minimum number // of operation static long minOperations(long N) { if (N < 0) return -1; long count = 0; while (N > 0) { long divisor = findElement(N); N -= divisor; count++; } return count; } // Driver code public static void Main() { long N = 5; Console.WriteLine(minOperations(N)); } } // This code is contributed by Samim Hossain Mondal.
Javascript
<script> // JavaScript program to minimize operations // to reduce N to 0 by replacing // N by its divisor at each step const findElement = (N) => { for (let i = 2; i * i <= N; i++) { if (N % i == 0) return parseInt(N / i); } return 1; } // Function to count minimum number // of operation const minOperations = (N) => { if (N < 0) return -1; let count = 0; while (N) { let divisor = findElement(N); N -= divisor; count++; } return count; } // Driver code let N = 5; document.write(minOperations(N)); // This code is contributed by rakeshsahni </script>
4
Complejidad de tiempo: O(N^(3/2))
Espacio auxiliar: O(1)
Enfoque eficiente: la solución anterior se puede optimizar mediante el cálculo previo utilizando el Tamiz de Eratóstenes para el factor primo más pequeño y modificándolo un poco para almacenar el factor más alto de N.
Siga los pasos a continuación para resolver este problema:
- Calcule previamente el tamiz usando el tamiz de Eratóstenes para el factor primo mínimo de números hasta N
- Modifique el tamiz anterior almacenando 1 para todos los valores cero ; de lo contrario, i/sieve[i] para cada i-ésimo valor
- Atraviese hasta que N se convierta en 0 .
- Reste sieve[N] para cada iteración de N .
- Cuente el número de iteraciones requeridas para que N se convierta en 0 de esta manera.
- Devuelva el recuento calculado anteriormente como la respuesta final.
C++14
// C++ program to minimize operations // to reduce N to 0 by replacing // N by its divisor at each step #include <bits/stdc++.h> using namespace std; typedef long long ll; #define MAX 10000001 ll sieve[MAX]; // Function to calculate sieve void makeSieve() { ll i, j; sieve[0] = 0; sieve[1] = 1; for (i = 2; i < MAX; i++) sieve[i] = 0; for (i = 2; i * i <= MAX; i++) { if (!sieve[i]) { sieve[i] = i; for (j = i * i; j < MAX; j += i) if (!sieve[j]) sieve[j] = i; } } for (i = 2; i < MAX; i++) { if (!sieve[i]) sieve[i] = 1; else sieve[i] = i / sieve[i]; } } // Function to count minimum operations ll minOperations(ll& N) { if (N < 0) return -1; ll count = 0; makeSieve(); while (N) { N -= sieve[N]; count++; } return count; } // Driver Code int main() { ll N = 8; cout << minOperations(N); return 0; }
Java
// JAVA code to implement the above approach import java.util.*; class GFG { static int MAX= 10000001; static int[] sieve = new int[MAX]; // Function to calculate sieve static void makeSieve() { int i, j; sieve[0] = 0; sieve[1] = 1; for (i = 2; i < MAX; i++) sieve[i] = 0; for (i = 2; i * i <= MAX; i++) { if (sieve[i]==0) { sieve[i] = i; for (j = i * i; j < MAX; j += i) if (sieve[j]==0) sieve[j] = i; } } for (i = 2; i < MAX; i++) { if (sieve[i]==0) sieve[i] = 1; else sieve[i] = i / sieve[i]; } } // Function to count minimum operations static int minOperations(int N) { if (N < 0) return -1; int count = 0; makeSieve(); while (N != 0) { N -= sieve[N]; count++; } return count; } // Driver code public static void main(String[] args) { int N = 8; System.out.print(minOperations(N)); } } // This code is contributed by sanjoy_62.
Python3
# Python3 code to implement the above approach MAX = 10000001 def makeSieve(): sieve = [0] * MAX sieve[1] = 1 for i in range(2, 1 + int(MAX ** 0.5)): if not sieve[i]: sieve[i] = i for j in range(i ** 2, MAX): if not sieve[j]: sieve[j] = i for i in range(2, MAX): if not sieve[i]: sieve[i] = 1 else: sieve[i] = (i // sieve[i]) return sieve def minOperations(N): if N < 0: return -1 count = 0 sieve = makeSieve() while N > 0: N -= (sieve[N]) count += 1 return count # Driver Code N = 8 print(minOperations(N))
C#
// C# implementation of above approach using System; class GFG{ static int MAX= 10000001; static int[] sieve = new int[MAX]; // Function to calculate sieve static void makeSieve() { int i, j; sieve[0] = 0; sieve[1] = 1; for (i = 2; i < MAX; i++) sieve[i] = 0; for (i = 2; i * i <= MAX; i++) { if (sieve[i]==0) { sieve[i] = i; for (j = i * i; j < MAX; j += i) if (sieve[j]==0) sieve[j] = i; } } for (i = 2; i < MAX; i++) { if (sieve[i]==0) sieve[i] = 1; else sieve[i] = i / sieve[i]; } } // Function to count minimum operations static int minOperations(int N) { if (N < 0) return -1; int count = 0; makeSieve(); while (N != 0) { N -= sieve[N]; count++; } return count; } // Driver Code static public void Main (){ int N = 8; Console.Write(minOperations(N)); } } // This code is contributed by code_hunt.
Javascript
<script> // JavaScript program to minimize operations // to reduce N to 0 by replacing // N by its divisor at each step let MAX = 10000001 let sieve= new Array(MAX); // Function to calculate sieve function makeSieve() { let i, j; sieve[0] = 0; sieve[1] = 1; for (i = 2; i < MAX; i++) sieve[i] = 0; for (i = 2; i * i <= MAX; i++) { if (!sieve[i]) { sieve[i] = i; for (j = i * i; j < MAX; j += i) if (!sieve[j]) sieve[j] = i; } } for (i = 2; i < MAX; i++) { if (!sieve[i]) sieve[i] = 1; else sieve[i] = i / sieve[i]; } } // Function to count minimum operations function minOperations(N) { if (N < 0) return -1; let count = 0; makeSieve(); while (N) { N -= sieve[N]; count++; } return count; } // Driver code let N = 8; // Function call document.write(minOperations(N)); // This code is contributed by jana_sayantan. </script>
4
Complejidad de tiempo: O(N * log(log N)
Espacio auxiliar: O(MAX), donde MAX es el límite para el tamiz (aquí MAX = 10000001).
Publicación traducida automáticamente
Artículo escrito por prophet1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA