Dado un número entero N , la tarea es reducir N a 1 con las siguientes dos operaciones:
- Se puede restar 1 de cada uno de los dígitos del número solo si el dígito es mayor que 0 y el número resultante no tiene ceros a la izquierda .
- 1 se puede restar del mismo número.
La tarea es encontrar el número mínimo de tales operaciones requeridas para reducir N a 1 .
Ejemplos:
Entrada: N = 35
Salida: 14
35 -> 24 -> 14 -> 13 -> 12 -> 11 -> 10 -> … -> 1 (14 operaciones)
Entrada: N = 240
Salida: 23
Enfoque: se puede observar que si el número es una potencia de 10 , es decir , N = 10 p , entonces el número de operaciones será (10 * p) – 1 . Por ejemplo, si N = 10 2 , las operaciones serán (10 * 2) – 2 = 19
, es decir , 100 -> 99 -> 88 -> 77 -> … -> 33 -> 22 -> 11 -> 10 -> 9 -> 8 -> … -> 2 -> 1 .
Ahora, la tarea es primero convertir lo dado a una potencia de 10 con las operaciones dadas y luego contar el número de operaciones requeridas para reducir esa potencia de 10 a 1. La suma de estas operaciones es la respuesta requerida. El número de operaciones requeridas para convertir un número a una potencia de será max(first_digit – 1, second_digit, third_digit, …, last_digit) , esto se debe a que cada dígito se puede reducir a 0, pero el primer dígito debe ser 1 para que es una potencia de 10 con igual número de dígitos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum number of
// given operations required to reduce n to 1
long long int minOperations(long long int n)
{
// To store the count of operations
long long int count = 0;
// To store the digit
long long int d = 0;
// If n is already then no
// operation is required
if (n == 1)
return 0;
// Extract all the digits except
// the first digit
while (n > 9) {
// Store the maximum of that digits
d = max(n % 10, d);
n /= 10;
// for each digit
count += 10;
}
// First digit
d = max(d, n - 1);
// Add the value to count
count += abs(d);
return count - 1;
}
// Driver code
int main()
{
long long int n = 240;
cout << minOperations(n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the minimum number of
// given operations required to reduce n to 1
static long minOperations(long n)
{
// To store the count of operations
long count = 0;
// To store the digit
long d = 0;
// If n is already then no
// operation is required
if (n == 1)
return 0;
// Extract all the digits except
// the first digit
while (n > 9)
{
// Store the maximum of that digits
d = Math.max(n % 10, d);
n /= 10;
// for each digit
count += 10;
}
// First digit
d = Math.max(d, n - 1);
// Add the value to count
count += Math.abs(d);
return count - 1;
}
// Driver code
public static void main (String[] args)
{
long n = 240;
System.out.println(minOperations(n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the minimum number of # given operations required to reduce n to 1 def minOperations(n): # To store the count of operations count = 0 # To store the digit d = 0 # If n is already then no # operation is required if (n == 1): return 0 # Extract all the digits except # the first digit while (n > 9): # Store the maximum of that digits d = max(n % 10, d) n //= 10 # for each digit count += 10 # First digit d = max(d, n - 1) # Add the value to count count += abs(d) return count - 1 # Driver code if __name__ == '__main__': n = 240 print(minOperations(n)) # This code is contributed by ashutosh450
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the minimum number of
// given operations required to reduce n to 1
static long minOperations(long n)
{
// To store the count of operations
long count = 0;
// To store the digit
long d = 0;
// If n is already then no
// operation is required
if (n == 1)
return 0;
// Extract all the digits except
// the first digit
while (n > 9)
{
// Store the maximum of that digits
d = Math.Max(n % 10, d);
n /= 10;
// for each digit
count += 10;
}
// First digit
d = Math.Max(d, n - 1);
// Add the value to count
count += Math.Abs(d);
return count - 1;
}
// Driver code
public static void Main (String[] args)
{
long n = 240;
Console.WriteLine(minOperations(n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum number of
// given operations required to reduce n to 1
function minOperations( n)
{
// To store the count of operations
var count = 0;
// To store the digit
var d = 0;
// If n is already then no
// operation is required
if (n == 1)
return 0;
// Extract all the digits except
// the first digit
while (n > 9) {
// Store the maximum of that digits
d = Math.max(n % 10, d);
n /= 10;
// for each digit
count += 10;
}
// First digit
d = Math.max(d, n - 1);
// Add the value to count
count += Math.abs(d);
return count - 1;
}
var n = 240;
document.write(minOperations(n));
// This code is contributed by SoumikMondal
</script>
23
Complejidad de tiempo: O (log 10 n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA