Representar un número como la suma de números positivos que terminan en 9

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 + 129

Entrada: 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 ² )
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:

1. Extraiga el último dígito del número dado, K = N % 10
2. 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 .
3. 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++ 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 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 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# 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

<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)