Dado un número entero N , la tarea es comprobar si N se puede expresar como una suma de números enteros que tienen 9 como último dígito (9, 19, 29, 39…), o no. Si se determina que es cierto, encuentre el recuento mínimo de dichos enteros necesarios para obtener N . De lo contrario, imprima -1 .
Ejemplos:
Entrada: N = 156
Salida: 4
Explicación:
156 = 9 + 9 + 9 + 129Entrada: N = 60
Salida: -1
Explicación:
No hay forma posible de obtener la suma 60 de números que tienen 9 como último dígito.
Enfoque ingenuo: este problema puede verse como una variación del problema de cambio de moneda . Para este problema, las monedas se pueden reemplazar con [9, 19, 29, 39…. hasta el último número menor que N que termina en 9].
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar basándose en la observación de que si el último dígito de N es K , entonces se requieren exactamente (10 – K) números mínimos para formar N .
Se puede obtener una suma N sumando 10 – K números, donde K es el último dígito de N.
Por lo tanto, la suma N se puede obtener sumando 9, (9 – K) veces y sumando N – (9 * (9 – K )) finalmente.
Siga los pasos a continuación para resolver el problema:
- Extraiga el último dígito del número dado, K = N % 10
- Usando la observación anterior, se requiere un total de (10 – K) números. Ahora, calcule 9 * (9 – K) , ya que los primeros 9 – K números necesarios para obtener N son 9 .
- Ahora, calcule N – 9 * (9 – K) y almacene en una variable, digamos z . Si z es mayor o igual a 9 y tiene 9 como último dígito, escriba 10 – K como respuesta. De lo contrario, imprima -1 .
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 count // of numbers ending with 9 to form N int minCountOfNumbers(int N) { // Extract last digit of N int k = N % 10; // Calculate the last digit int z = N - (9 * (9 - k)); // If the last digit // satisfies the condition if (z >= 9 && z % 10 == 9) { return 10 - k; } else return -1; } // Driver Code int main() { int N = 156; cout << minCountOfNumbers(N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the minimum count // of numbers ending with 9 to form N static int minCountOfNumbers(int N) { // Extract last digit of N int k = N % 10; // Calculate the last digit int z = N - (9 * (9 - k)); // If the last digit // satisfies the condition if (z >= 9 && z % 10 == 9) { return 10 - k; } else return -1; } // Driver Code public static void main(String[] args) { int N = 156; System.out.print(minCountOfNumbers(N)); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find the minimum count # of numbers ending with 9 to form N def minCountOfNumbers(N): # Extract last digit of N k = N % 10 # Calculate the last digit z = N - (9 * (9 - k)) # If the last digit # satisfies the condition if (z >= 9 and z % 10 == 9): return 10 - k else: return -1 # Driver Code if __name__ == '__main__': N = 156 print(minCountOfNumbers(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 count // of numbers ending with 9 to form N static int minCountOfNumbers(int N) { // Extract last digit of N int k = N % 10; // Calculate the last digit int z = N - (9 * (9 - k)); // If the last digit // satisfies the condition if (z >= 9 && z % 10 == 9) { return 10 - k; } else return -1; } // Driver Code public static void Main(String[] args) { int N = 156; Console.Write(minCountOfNumbers(N)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // java script program for the above approach // Function to find the minimum count // of numbers ending with 9 to form N function minCountOfNumbers(N){ // Extract last digit of N let k = N % 10; // Calculate the last digit let z = N - (9 * (9 - k)); // If the last digit // satisfies the condition if (z >= 9 && z % 10 == 9) { return 10 - k; } else { return -1; } } // Driver Code let N = 156; document.write(minCountOfNumbers(N)); // This code is contributed by sravan kumar </script>
4
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA