Узнайте минимальное количество монет, необходимое для выплаты общей суммы

Опубликовано: 14 Января, 2022

Учитывая общее количество N и неограниченное количество монет стоимостью 1 , 10 и 25 валютных монет. Выясните минимальное количество монет, которое вам нужно использовать для выплаты ровно суммы N.
Примеры:

 Ввод: N = 14
Выход: 5
Вы будете использовать один код 10 и 
четыре монеты достоинством 1.

Ввод : N = 88.
Выход : 7

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:
Есть три разных случая:

  1. Если значение N <10, то монеты со значением 1 можно использовать только для оплаты.
  2. Когда N > 9 и <25, то для выплаты будут использоваться монеты достоинством 1 и 10. Здесь, чтобы минимизировать количество используемых монет, в основном будут предпочтительны монеты номиналом 10.
  3. Когда N > 24. Тогда все монеты достоинством 1, 10 и 25 будут использованы для выплаты. Чтобы свести к минимуму количество монет, основная цель будет заключаться в том, чтобы сначала максимально использовать монету номиналом 25, затем монету достоинством 10, а затем - 1.

Below is the implementation of the above approach:
 

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>
Output: 
5

 

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ