Узнайте минимальное количество монет, необходимое для выплаты общей суммы
Опубликовано: 14 Января, 2022
Учитывая общее количество N и неограниченное количество монет стоимостью 1 , 10 и 25 валютных монет. Выясните минимальное количество монет, которое вам нужно использовать для выплаты ровно суммы N.
Примеры:
Ввод: N = 14 Выход: 5 Вы будете использовать один код 10 и четыре монеты достоинством 1. Ввод : N = 88. Выход : 7
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход:
Есть три разных случая:
- Если значение N <10, то монеты со значением 1 можно использовать только для оплаты.
- Когда N > 9 и <25, то для выплаты будут использоваться монеты достоинством 1 и 10. Здесь, чтобы минимизировать количество используемых монет, в основном будут предпочтительны монеты номиналом 10.
- Когда 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.