Dado un número N , la tarea es encontrar el número mínimo de operaciones requeridas para reducir el número N a cero restando el número dado por cualquier dígito presente en él.
Ejemplos:
Entrada: N = 4
Salida: 1
Explicación:
Aquí 4 es el único dígito presente, por lo tanto, 4 – 4 = 0 y solo se requiere una operación.Entrada: N = 17
Salida: 3
Explicación:
El número entero dado es 17 y los pasos de reducción son:
17 -> 17 – 7 = 10
10 -> 10 – 1 = 9
9 -> 9 – 9 = 0.
Por lo tanto, 3 operaciones son requeridos.
Enfoque: Este problema se puede resolver usando Programación Dinámica .
Para cualquier número dado N , recorra cada dígito en N y verifique recursivamente restando cada dígito uno por uno hasta que N se reduzca a 0 . Pero realizar la recursividad hará que la complejidad temporal del enfoque sea exponencial.
Por lo tanto, la idea es usar una array (por ejemplo , dp[] ) de tamaño (N + 1) tal que dp[i] almacene el número mínimo de operaciones necesarias para reducir i a 0 .
Para cada dígito x en el número N , la relación de recurrencia utilizada viene dada por:
dp[i] = min(dp[i], dp[ix] + 1),
donde dp[i] almacenará el número mínimo de operaciones necesarias para reducir i a 0 .
Usaremos el enfoque ascendente para llenar la array dp[] de 0 a N y luego dp[N] dará el número mínimo de operaciones para N.
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 reduce an integer N // to Zero in minimum operations by // removing digits from N int reduceZero(int N) { // Initialise dp[] to steps vector<int> dp(N + 1, 1e9); dp[0] = 0; // Iterate for all elements for (int i = 0; i <= N; i++) { // For each digit in number i for (char c : to_string(i)) { // Either select the number // or do not select it dp[i] = min(dp[i], dp[i - (c - '0')] + 1); } } // dp[N] will give minimum // step for N return dp[N]; } // Driver Code int main() { // Given Number int N = 25; // Function Call cout << reduceZero(N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to reduce an integer N // to Zero in minimum operations by // removing digits from N static int reduceZero(int N) { // Initialise dp[] to steps int []dp = new int[N + 1]; for (int i = 0; i <= N; i++) dp[i] = (int) 1e9; dp[0] = 0; // Iterate for all elements for (int i = 0; i <= N; i++) { // For each digit in number i for (char c : String.valueOf(i).toCharArray()) { // Either select the number // or do not select it dp[i] = Math.min(dp[i], dp[i - (c - '0')] + 1); } } // dp[N] will give minimum // step for N return dp[N]; } // Driver Code public static void main(String[] args) { // Given Number int N = 25; // Function Call System.out.print(reduceZero(N)); } } // This code is contributed by amal kumar choubey
Python3
# Python3 program for the above approach # Function to reduce an integer N # to Zero in minimum operations by # removing digits from N def reduceZero(N): # Initialise dp[] to steps dp = [1e9 for i in range(N + 1)] dp[0] = 0 # Iterate for all elements for i in range(N + 1): # For each digit in number i for c in str(i): # Either select the number # or do not select it dp[i] = min(dp[i], dp[i - (ord(c) - 48)] + 1) # dp[N] will give minimum # step for N return dp[N] # Driver Code N = 25 # Function Call print(reduceZero(N)) # This code is contributed by Sanjit_Prasad
C#
// C# program for the above approach using System; class GFG{ // Function to reduce an integer N // to Zero in minimum operations by // removing digits from N static int reduceZero(int N) { // Initialise []dp to steps int []dp = new int[N + 1]; for (int i = 0; i <= N; i++) dp[i] = (int) 1e9; dp[0] = 0; // Iterate for all elements for (int i = 0; i <= N; i++) { // For each digit in number i foreach (char c in String.Join("", i).ToCharArray()) { // Either select the number // or do not select it dp[i] = Math.Min(dp[i], dp[i - (c - '0')] + 1); } } // dp[N] will give minimum // step for N return dp[N]; } // Driver Code public static void Main(String[] args) { // Given Number int N = 25; // Function Call Console.Write(reduceZero(N)); } } // This code is contributed by amal kumar choubey
Javascript
<script> // Javascript program for the above approach // Function to reduce an integer N // to Zero in minimum operations by // removing digits from N function reduceZero(N) { // Initialise dp[] to steps var dp = Array(N + 1).fill(1000000000); dp[0] = 0; // Iterate for all elements for (var i = 0; i <= N; i++) { // For each digit in number i for (var j =0; j< i.toString().length; j++) { // Either select the number // or do not select it dp[i] = Math.min(dp[i], dp[i - (i.toString()[j] - '0')] + 1); } } // dp[N] will give minimum // step for N return dp[N]; } // Driver Code // Given Number var N = 25; // Function Call document.write( reduceZero(N)); </script>
5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mridulkumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA