/*
Online Java - IDE, Code Editor, Compiler
Online Java is a quick and easy tool that helps you to build, compile, test your programs online.
*/
import java.util.Scanner;
import java.util.Arrays;

public class Main
{
    public static void main(String[] args) 
    {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        int [] coins = new int[]{1,5,10,25};
        int number;
        Scanner reader=null;
        int coinCount=0;
        // This is used to ascertain how many digits end user wants
        reader = new Scanner(System.in); // Reading from System.in
        System.out.println("Enter requested amount to be converted to coins:");
        number=reader.nextInt();
        coinChange cc = new coinChange(coins, number);
        
        System.out.println("\nThis is the number of coins: " + cc.getNumberCoins());
    }
}

class coinChange
{
    int[] coins;
    int number;
    int coinCount=0;
    
    public coinChange(int coins[], int number)
    {
        this.coins=coins;
        this.number=number;
        convertCoins(number);
    }
    
    public int convertCoins(int n)
    {
        if (number!=0)
        {
            for (int i=coins.length-1; i>=0; i--)
            {
                if (number==1)
                {
                    System.out.println(number + " can be broken down into following coin: " + coins[0]);
                    number=0;
                    System.out.println("This is the remainder: " + number);
                    coinCount++;
                    
                    return convertCoins(number);
                }
                
                if (number-coins[i]>=0)
                {
                    System.out.println(number + " can be broken down into following coin: " + coins[i]);
                    number=number-coins[i];
                    System.out.println("This is the remainder: " + number);
                    coinCount++;
                    
                    return convertCoins(number);
                }
            }
        }
        return 0;
    }
    
    public int getNumberCoins()
    {
        return coinCount;
    }
}