/
NikolayIvkin
/
TheAlgorithms
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/main/java/com/thealgorithms/greedyalgorithms/CoinChange.java
35 строк
1 KB
Piotr Idzik
style: enable `HideUtilityClassConstructor` in checkstyle (#5147)
08 май 2024, 09:58
Не верифицирован
08 май 2024, 09:58
d3bb691
Код
Авторство
О чём код?
package com.thealgorithms.greedyalgorithms; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; // Problem Link : https://en.wikipedia.org/wiki/Change-making_problem public final class CoinChange { private CoinChange() { } // Function to solve the coin change problem public static ArrayList<Integer> coinChangeProblem(int amount) { // Define an array of coin denominations in descending order Integer[] coins = {1, 2, 5, 10, 20, 50, 100, 500, 2000}; // Sort the coin denominations in descending order Arrays.sort(coins, Comparator.reverseOrder()); ArrayList<Integer> ans = new ArrayList<>(); // List to store selected coins // Iterate through the coin denominations for (int i = 0; i < coins.length; i++) { // Check if the current coin denomination can be used to reduce the remaining amount if (coins[i] <= amount) { // Repeatedly subtract the coin denomination from the remaining amount while (coins[i] <= amount) { ans.add(coins[i]); // Add the coin to the list of selected coins amount -= coins[i]; // Update the remaining amount } } } return ans; } }