Dado un número entero N , la tarea es encontrar el recuento mínimo de números que se deben sumar para obtener N . (Todos esos números deben tener 9 como dígito de uno)
Ejemplos:
Entrada: N = 27
Salida: 3
27 = 9 + 9 + 9Entrada: N = 109
Salida: 1
109 en sí mismo tiene 9 como dígito de uno.
Acercarse:
- Verifique el dígito de uno de N , según el dígito de uno, se puede encontrar fácilmente el recuento mínimo de números que deben agregarse.
- Si el dígito de uno es 9: La respuesta será 1 ya que el número en sí tiene 9 como dígito de lugar de uno.
- Si el dígito de uno es:
- 1: 9 tiene que sumarse 9 veces, es decir (9 * 9 = 81).
- 2: 9 tiene que sumarse 8 veces, es decir (9 * 8 = 72).
- 3: 9 tiene que sumarse 7 veces, es decir (9 * 7 = 63).
- 4: 9 tiene que sumarse 6 veces, es decir (9 * 6 = 54).
- 5: 9 tiene que sumarse 5 veces, es decir (9 * 5 = 45).
- 6: 9 tiene que sumarse 4 veces, es decir (9 * 4 = 36).
- 7: 9 se tiene que sumar 3 veces, es decir (9 * 3 = 27).
- 8: 9 tiene que sumarse 2 veces, es decir (9 * 2 = 18).
- 0: 9 tiene que sumarse 10 veces, es decir (9 * 10 = 90).
- La observación aquí es que solo se debe agregar el conteo múltiplo mínimo para todos los casos mencionados anteriormente. Esto se debe a que, por ejemplo, para el dígito de uno como 4 , se pueden usar todos los 9 (el lugar de uno) de 6 números y el resultado se puede restar de N , digamos que es M. Ahora, M tendrá 0 en lugar de uno. Entonces, solo use 5 números como 9 y el sexto número como (M + 9) .
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 find minimum count
// of numbers(with one's digit 9)
// that sum up to N
int findMin(int N)
{
// Fetch one's digit
int digit = N % 10;
// Apply Cases mentioned in approach
switch (digit) {
case 0:
if (N >= 90)
return 10;
break;
case 1:
if (N >= 81)
return 9;
break;
case 2:
if (N >= 72)
return 8;
break;
case 3:
if (N >= 63)
return 7;
break;
case 4:
if (N >= 54)
return 6;
break;
case 5:
if (N >= 45)
return 5;
break;
case 6:
if (N >= 36)
return 4;
break;
case 7:
if (N >= 27)
return 3;
break;
case 8:
if (N >= 18)
return 2;
break;
case 9:
if (N >= 9)
return 1;
break;
}
// If no possible answer exists
return -1;
}
// Driver code
int main()
{
int N = 27;
cout << findMin(N);
}
Java
// Java implementation of the approach
class GFG
{
// Function to find minimum count
// of numbers(with one's digit 9)
// that sum up to N
static int findMin(int N)
{
// Fetch one's digit
int digit = N % 10;
// Apply Cases mentioned in approach
switch (digit)
{
case 0:
if (N >= 90)
return 10;
break;
case 1:
if (N >= 81)
return 9;
break;
case 2:
if (N >= 72)
return 8;
break;
case 3:
if (N >= 63)
return 7;
break;
case 4:
if (N >= 54)
return 6;
break;
case 5:
if (N >= 45)
return 5;
break;
case 6:
if (N >= 36)
return 4;
break;
case 7:
if (N >= 27)
return 3;
break;
case 8:
if (N >= 18)
return 2;
break;
case 9:
if (N >= 9)
return 1;
break;
}
// If no possible answer exists
return -1;
}
// Driver code
public static void main (String[] args)
{
int N = 27;
System.out.println(findMin(N));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to find minimum count # of numbers(with one's digit 9) # that sum up to N def findMin(N: int): # Fetch one's digit digit = N % 10 # Apply Cases mentioned in approach if digit == 0 and N >= 90: return 10 elif digit == 1 and N >= 81: return 9 elif digit == 2 and N >= 72: return 8 elif digit == 3 and N >= 63: return 7 elif digit == 4 and N >= 54: return 6 elif digit == 5 and N >= 45: return 5 elif digit == 6 and N >= 36: return 4 elif digit == 7 and N >= 27: return 3 elif digit == 8 and N >= 18: return 2 elif digit == 9 and N >= 9: return 1 # If no possible answer exists return -1 # Driver Code if __name__ == "__main__": N = 27 print(findMin(N)) # This code is contributed by # sanjeev2552
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find minimum count
// of numbers(with one's digit 9)
// that sum up to N
static int findMin(int N)
{
// Fetch one's digit
int digit = N % 10;
// Apply Cases mentioned in approach
switch (digit)
{
case 0:
if (N >= 90)
return 10;
break;
case 1:
if (N >= 81)
return 9;
break;
case 2:
if (N >= 72)
return 8;
break;
case 3:
if (N >= 63)
return 7;
break;
case 4:
if (N >= 54)
return 6;
break;
case 5:
if (N >= 45)
return 5;
break;
case 6:
if (N >= 36)
return 4;
break;
case 7:
if (N >= 27)
return 3;
break;
case 8:
if (N >= 18)
return 2;
break;
case 9:
if (N >= 9)
return 1;
break;
}
// If no possible answer exists
return -1;
}
// Driver code
public static void Main (String[] args)
{
int N = 27;
Console.WriteLine(findMin(N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to find minimum count
// of numbers(with one's digit 9)
// that sum up to N
function findMin(N)
{
// Fetch one's digit
let digit = N % 10;
// Apply Cases mentioned in approach
switch (digit)
{
case 0:
if (N >= 90)
return 10;
break;
case 1:
if (N >= 81)
return 9;
break;
case 2:
if (N >= 72)
return 8;
break;
case 3:
if (N >= 63)
return 7;
break;
case 4:
if (N >= 54)
return 6;
break;
case 5:
if (N >= 45)
return 5;
break;
case 6:
if (N >= 36)
return 4;
break;
case 7:
if (N >= 27)
return 3;
break;
case 8:
if (N >= 18)
return 2;
break;
case 9:
if (N >= 9)
return 1;
break;
}
// If no possible answer exists
return -1;
}
// Driver code
let N = 27;
document.write(findMin(N));
// This code is contributed by souravmahato348
</script>
Producción:
3
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)