# Modulo operator on greedy?

Maybe it's a ridiculous question; I've watched several times the CS50 videos (greedy) and I don't get the point using modulo on greedy. Maybe I don't know what to do after I ask the user an input...

When you code for greedy, you'll need to do two things as you're counting the coins. You need to figure out how many coins of a given denomination (quarters, dimes, etc.) are needed and then how much change is left after you account for them.

Now, without giving away any other aspects of the assignment, let's say you are working in a fictional currency that has the coins of foos and bars. A foo is 4 bars. So, if you had to convert 10 bars to the minimum number of coins, you'd do integer division first, 10/4 = 2 foos. But you also need to know how many bars are left over. That's where the % comes in. 10 % 4 will give you 2, so you'd have 2 bars left as change. The total coins would be 4 -> 2 foos and 2 bars. That's what you do with the % operator. If you have more types of coins, then you just repeat the process on the remaining change.

If this answers your question, please click on the check to accept. Let's keep up on forum housekeeping. ;-)

I think using a series of loops and subtraction is a bit more straightforward and easier to understand/picture.

You can think of using the modulo operator in this problem as hacking away at chunks of the user's input. Using loops and subtraction, you iterate over the user's input over and over again taking away set, incremental bits each time you run a loop. The modulo operator (dividing number 1 by number 2 and then returning the remainder) will eliminate a lot of this iteration and will make a faster program.

For example, say a user inputs \$1.00. Using subtraction, the computer could take away 0.25 with every loop execution equaling four iterations and thus four coins. Using modulo however, you can do this in one iteration of a loop.

• Let's look at the efficiency of that. To make it really clear, let's say that the input is \$1000.00. Also, we'll only look at counting quarters. If you use a while loop, you have to execute at least three steps - 1) test that you're over a quarter in the while loop control statement and 2) subtract a quarter from the running total, and 3) increment the coin count. That means that you have to execute 4000 steps to calculate how many quarters you have. When the running total is under a quarter, that gives you the change, so it's included in the 4000 steps. (continues....) Oct 14 '15 at 15:36
• Now, if instead, you do an integer division to determine the quarters, followed by a modulo to determine the remainder, then you have accomplished the same goal in 2 steps. The execution in computer time is 2k times more efficient! While it may not seem to be a significant time difference for the single task of the pset, program efficiency becomes critical when writing practical programs that must run the same task millions of times. (continues....) Oct 14 '15 at 15:42
• For example, I was recently asked to help with a program to confirm that a 1 million word file contained all unique words. The current solution was estimated to take 11 days to execute. We wrote another program to do the same check that took 0.61 seconds to do the same task. This shows how easy it can be to write a very inefficient program and how important it can be to write efficient code. Oct 14 '15 at 15:44
• Beautifully said! Oct 14 '15 at 15:45
• Oops, I was wrong. It isn't 4000 steps, it's 4000 loops - 12,000 steps. I should really be more careful. ;-) Oct 14 '15 at 15:46