hi i have a lab to do and i'm stuck on how to start a method

i have 10 coins and i want to write a method that tells me the fewest amount of coins needed to add up to 100 - 1 dollar

coins are randomly generated - values are 1,5,10,25
in a coin class

the method is in the usecoin class

i understand that there is a possibility of all 10 coins dont add up to 100
i'm going to ignore that for now and maybe add an error message not enough coins

can anyone help give me some ideas on how to start this method?

5 Years
Discussion Span
Last Post by blahbla

When in doubt, try doing it by hand and see what steps you need to take. Here's a random collection of coins: 3 quarters, two dimes, three nickels, and two pennies.

Here's another random collection: 4 quarters, 4 dimes, 1 nickel, and 1 penny.

Here's another random collection: 1 quarter, 1 dime, 1 nickel, and 7 pennies.

How do you find the smallest number to make up a dollar in each case?


ok so it's

100 - quarters = remainder and subtract(dimes, nickel, penny) till it reaches 0
and count ++ till it ends
if it becomes negative then add the previous and count -- then continue with the next set

something like this

ok then if

Coin[] wallet;
		wallet = new Coin[10];

i cant compare wallet with an int
i cant say something like

int sum = 0;
sum = sum + w;
if(w == 25)

how do i compare it or what do i have to do so that i can?
my professor mentioned something about vectors
but his explanation wasnt clear and he didnt really teach how to write stuff in java lang

Edited by blahbla: n/a


I'm not sure if I'm following your algorithm. You have to be more specific.

Suppose I have 1 quarter, eight dimes, and a nickel.
What is the order of operations? What values do you need to keep track of? What do you need to check, and when?

Don't get into implementation details yet - you're still trying to figure out what your algorithm looks like. We don't care about arrays and vectors and stuff yet, we just need to know how to solve the problem.


ok sort it first if needed count how many of each there is

then it would look something like

25 25 25 10 10 10 5 5 1 1

then my total would be 100, i need to get 100
i can add the numbers one by one from first number to last and try to get 100
or i can subtract numbers from 100, one by one from first number to last

if the total becomes greater than 100 or less than 0
then i have to add back or subtract the previous number then continue from then on

i would have a count to count how many numbers i used
and this too will change if the total is greater than 100 or less than 0

Edited by blahbla: n/a


Okay, I think that's a little better. If the procedure is becoming more clear in your mind, that's the point of this. The sorting is important - it tells me that you're thinking about the order in which you're handling the data. (and yes, you do want to handle the largest items first)

You seem to like the idea of backtracking. "If the number is negative, add the previous value back in and continue" This gets complicated. Is there any way to check whether the value would be negative, and just use that coin in that case?

Now think about representation. How are you going to represent the data?
It looks like you're treating each coin as an item, so you have an array of coins[], and you maybe have coins[0]=25, coins[1]=10, coins[2]=2, and so forth.

Is this the best way to keep track of this? How else could you do this, and would that change the way you solve the problem? For example, look at the way I've specified example scenarios for you. I didn't tell you "The first coin is a quarter, the second coin is a quarter, the third coin is a dime, ...", did I?
Maybe the teacher has you doing this with an array of coins - if so, you'll do it that way. But is that the best way?


are you talking about something like this or in this sense?

how_many_quarters = 3;
how_many_dimes = 3;
how_many_nickels = 2;
how_many_pennies = 2;

hmmm but i have to use the array of coins
i have to create another class call coins that stores the values and the face of the coins
can return values and face
a default constructor that generates the numbers and flips the coin
a toCompare method that compares coin objects with other coin objects
a toString method that allows just System.out.println(object_name); to print


Yeah, that's what I had in mind. But okay, so you have an array of coins. Write your Coin object first. Shouldn't take you long. Make sure you look at the Comparable interface when you're writing your compareTo method. That'll let you sort the array, like you were saying you wanted to do.
Your toString method shouldn't print the value, by the way - it should return the value that should be printed. That's important. So the signature should be

public String toString() {}

Once you have your Coin class written, you'll put Coins into an array and sort it, as you said. Then you remove them from the array, one at a time, and make decisions. Think about those decisions while you're writing Coin, and come back with a prototype.


this is the code for the coin class most of it is written by the professor

all i had to do was make it so the constructor produces the values 1,5,10,25 randomly

the work i have to do is mostly in another class called UseCoin

public class Coin{
	public static final int HEADS = 0;
	public static final int TAILS = 1;

	private int value = 1;
	private int face;
	public Coin(){
		int v = (int)(Math.random()*4);
		case 0:
			value = 1;
		case 1:
			value = 5;
		case 2:
			value = 10;
		case 3:
			value = 25;
	public void flip(){
		face = (int)(Math.random()*2);
	public int getValue(){
		return value;
	public String getFace(){
		if (face == HEADS)
			return "HEADS";
			return "TAILS";
	public String toString(){
		return "Value: " + value + ", Face: " + getFace(); 
	public int compareTo(Coin coin){
		if(value == coin.getValue()){
			return 0;
		else if(value < coin.getValue()){
				return -1;
			else return 1;

ok problem solved got it to work now i have to figure out how to find the maximum number of coins needed

thanks for all the help jon

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.