Dada una cantidad total de N y un número ilimitado de monedas por valor de 1 , 10 y 25 monedas. Averigüe la cantidad mínima de monedas que necesita usar para pagar exactamente la cantidad N .
Ejemplos:
Input : N = 14 Output : 5 You will use one coin of value 10 and four coins of value 1. Input : N = 88 Output : 7
Planteamiento:
Hay tres casos diferentes:
- Si el valor de N < 10, entonces las monedas que tienen el valor 1 solo se pueden usar para el pago.
- Cuando N > 9 y < 25, se utilizarán para el pago monedas que tengan valor 1 y 10. Aquí, para minimizar el número de monedas utilizadas, se preferirán principalmente las monedas con un valor de 10.
- Cuando N > 24. Entonces todas las monedas de valor 1, 10 y 25 se utilizarán para el pago. Para minimizar el número de monedas, el objetivo principal será usar monedas con valor 25 primero tanto como sea posible, luego monedas con valor 10 y luego con valor 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum number
// of coins required
#include <iostream>
using namespace std;
// Function to find the minimum number
// of coins required
int countCoins(int n)
{
int c = 0;
if (n < 10) {
// counts coins which have value 1
// we will need n coins of value 1
return n;
}
if (n > 9 && n < 25) {
// counts coins which have value 1 and 10
c = n / 10 + n % 10;
return c;
}
if (n > 24) {
// counts coins which have value 25
c = n / 25;
if (n % 25 < 10) {
// counts coins which have value 1 and 25
c = c + n % 25;
return c;
}
if (n % 25 > 9) {
// counts coins which have value 1, 10 and 25
c = c + (n % 25) / 10 + (n % 25) % 10;
return c;
}
}
}
// Driver Code
int main()
{
int n = 14;
cout << countCoins(n);
return 0;
}
Java
// Java program to find the minimum number
// of coins required
class GFG {
// Function to find the minimum number
// of coins required
static int countCoins(int n)
{
int c = 0;
if (n < 10) {
// counts coins which have value 1
// we will need n coins of value 1
return n;
}
if (n > 9 && n < 25) {
// counts coins which have value 1 and 10
c = n / 10 + n % 10;
return c;
}
if (n > 24) {
// counts coins which have value 25
c = n / 25;
if (n % 25 < 10) {
// counts coins which have value 1 and 25
c = c + n % 25;
return c;
}
if (n % 25 > 9) {
// counts coins which have value 1, 10 and 25
c = c + (n % 25) / 10 + (n % 25) % 10;
return c;
}
}
return c;
}
// Driver Code
public static void main(String[] args)
{
int n = 14;
System.out.println(countCoins(n));
}
}
Python3
# Python3 program to find the minimum number # of coins required # Function to find the minimum number # of coins required def countCoins(n): c = 0 if (n < 10): # counts coins which have value 1 # we will need n coins of value 1 return n if (n > 9 and n < 25): # counts coins which have value 1 and 10 c = n // 10 + n % 10 return c if (n > 24): # counts coins which have value 25 c = n // 25 if (n % 25 < 10): # counts coins which have value # 1 and 25 c = c + n % 25 return c if (n % 25 > 9): # counts coins which have value # 1, 10 and 25 c = (c + (n % 25) // 10 + (n % 25) % 10) return c # Driver Code n = 14 print(countCoins(n)) # This code is contributed by mohit kumar
C#
// C# program to find the minimum number
// of coins required
using System;
class GFG
{
// Function to find the minimum number
// of coins required
static int countCoins(int n)
{
int c = 0;
if (n < 10)
{
// counts coins which have value 1
// we will need n coins of value 1
return n;
}
if (n > 9 && n < 25)
{
// counts coins which have value 1 and 10
c = n / 10 + n % 10;
return c;
}
if (n > 24)
{
// counts coins which have value 25
c = n / 25;
if (n % 25 < 10)
{
// counts coins which have value 1 and 25
c = c + n % 25;
return c;
}
if (n % 25 > 9)
{
// counts coins which have value 1, 10 and 25
c = c + (n % 25) / 10 + (n % 25) % 10;
return c;
}
}
return c;
}
// Driver Code
public static void Main()
{
int n = 14;
Console.WriteLine(countCoins(n));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP program to find the minimum number
// of coins required
// Function to find the minimum number
// of coins required
function countCoins($n)
{
$c = 0;
if ($n < 10)
{
// counts coins which have value 1
// we will need n coins of value 1
return $n;
}
if ($n > 9 && $n < 25)
{
// counts coins which have value 1 and 10
$c = (int)($n / 10 + $n % 10);
return $c;
}
if ($n > 24)
{
// counts coins which have value 25
$c = (int)($n / 25);
if ($n % 25 < 10)
{
// counts coins which have value 1 and 25
$c = $c + $n % 25;
return $c;
}
if ($n % 25 > 9)
{
// counts coins which have value 1, 10 and 25
$c = $c + ($n % 25) / 10 + ($n % 25) % 10;
return $c;
}
}
return $c;
}
// Driver Code
$n = 14;
echo(countCoins($n));
// This code is contributed Code_Mech
Javascript
<script>
// JavaScript program to find the minimum number
// of coins required
// Function to find the minimum number
// of coins required
function countCoins( n)
{
var c = 0;
if (n < 10)
{
// counts coins which have value 1
// we will need n coins of value 1
return n;
}
if (n > 9 && n < 25)
{
// counts coins which have value 1 and 10
c = n / 10 + n % 10;
return Math.trunc(c);
}
if (n > 24)
{
// counts coins which have value 25
c = n / 25;
if (n % 25 < 10)
{
// counts coins which have value 1 and 25
c = c + n % 25;
return Math.trunc(c);
}
if (n % 25 > 9)
{
// counts coins which have value 1, 10 and 25
c = c + (n % 25) / 10 + (n % 25) % 10;
return Math.trunc(c);
}
}
}
var n = 14;
document.write(countCoins(n));
// This code is contributed by akshitsaxenaa09.
</script>
Producción:
5
Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por facebookruppal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA