Greedy Algorithm

Question

I am writing a piece of code, when a user enters the amount of change owed, returns the minimum amount of coins to equal that change. For instance, assuming only quarters, dimes, nickels and pennies are used. You enter $1.00. The number my code will render on the screen is 4 (4 quarters equaling a dollar). However, I am experiencing a small bug. If you type in $0.41 for example, you'd expect the code to render 4 again (1 quarter + 1 dime + 1 nickel + 1 penny is the minimum amount of permutations to equal 41 cents), but it doesn't, it renders 5.44. Please help! Thank you in advance.

document.write("Hi,how much change is due? ");

function greed () {
	
	var n = document.getElementById('change').value;
	
	if (n >=0)
	{ 
		
	
		function amount (amt){
			
				return amt/25 + (amt%25)/10 + ((amt%25)%10)/5 + ((amt%25)%10)%5;
				
			 }
		document.write(amount(Math.round(n*100)));
	}
	else {alert("Invalid Amount!")};
}

<!DOCTYPE html>

<html lang="en-US">

	<head>

		<title>Greedy! </title>
		<script type="text/javascript" src="greedy.js" ></script>
	</head>

	<body>
		<form>
			<fieldset>
				<input type="number" id="change" name="change" value="0"/>
				<input type="submit" id="submit" name="submit" value="submit" onclick="greed();"/>
		
			</fieldset>
		</form>
	</body>

</html>

and if you write 0.1 it returns 1.4. You're missing something very important there — Shinra tensei

Shinra tensei Shinra tensei · Accepted Answer · 2017-09-22T08:35:36

The main problem here is that you're not treating the numbers as integers, so you get decimal numbers everywhere. Let's use your example (0.41):

amt = n*100 = 41, so let's go to the return:

return amt/25 + (amt%25)/10 + ((amt%25)%10)/5 + ((amt%25)%10)%5

which is the same as

return 41/25 + (41%25)/10 + ((41%25)%10)/5 + ((41%25)%10)%5

as you know, 41/25 =/= 1, same with (41%25)/10 = 16/10 =/= 1 and ((41%25)%10)/5 = (16%10)/5 = 6/5 =/= 1, but you don't care about that in the code so you end up adding those decimal numbers till the end, and get weird values.

You must use parseInt() to get Integer values, so it should look like this:

return parseInt(amt/25) + parseInt((amt%25)/10) + parseInt(((amt%25)%10)/5) + ((amt%25)%10)%5

To show it works:

document.write("Hi,how much change is due? ");

function greed () {
	
	var n = document.getElementById('change').value;
	
	if (n >=0)
	{ 
		
	
		function amount (amt){
			
				return parseInt(amt/25) + parseInt((amt%25)/10) + parseInt(((amt%25)%10)/5) + ((amt%25)%10)%5;
				
			 }
		document.write(amount(Math.round(n*100)));
	}
	else {alert("Invalid Amount!")};
}

<!DOCTYPE html>

<html lang="en-US">

	<head>

		<title>Greedy! </title>
		<script type="text/javascript" src="greedy.js" ></script>
	</head>

	<body>
		<form>
			<fieldset>
				<input type="number" id="change" name="change" value="0"/>
				<input type="submit" id="submit" name="submit" value="submit" onclick="greed();"/>
		
			</fieldset>
		</form>
	</body>

</html>

Greedy Algorithm

1 Answers