5
\$\begingroup\$

Description:

The goal in this problem is to find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10

The input consists of a single integer m.

1≤m≤103

Output the minimum number of coins with denominations 1, 5, 10 that changes m.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{

  public static int CountChange(int m) {
    if (m <= 0) return 0;

    int[] denomenations = new int[]{10, 5, 1};
    int change = 0; 

    for (int i : denomenations) {
      while (m - i >= 0) {
        m -= i;
        change++;
      }
    }

    return change;
  }

    public static void main (String[] args) throws java.lang.Exception
    {
      // edge cases
      System.out.println(CountChange(0));  // 0
      System.out.println(CountChange(-1)); // 0
      System.out.println(CountChange(Integer.MIN_VALUE)); // 0
      System.out.println(CountChange(Integer.MAX_VALUE));

      System.out.println(CountChange(1));  // 1 = 1
      System.out.println(CountChange(2));  // 2 = 1 + 1
      System.out.println(CountChange(5));  // 1 = 5
      System.out.println(CountChange(10)); // 1 = 10
      System.out.println(CountChange(28)); // 6 = 10 + 10 + 5 + 1 + 1 + 1
    }
}

Questions

  1. This seems exponential algorithm to me but what is the correct approach for finding the running time of this algorithm?
  2. I put some thoughts on testing strategies in this problem, since the input is integer I had few number of edge cases also the problem description doesn't cover edge cases (e.g.: maximum integer) but then also I thought to test it, is this the correct approach?
  3. For m = 0 the algorithm works fine but still I gave a guard condition for readability, don't know if this is a good strategy.
  4. I think that a better algorithm can be developed and suggestions are welcome.
\$\endgroup\$
  • 1
    \$\begingroup\$ Note that this greed algorithm works for these particular denominations, but won't work for certain other denomination sets. \$\endgroup\$ – CodesInChaos Sep 21 '16 at 20:46
  • 1
    \$\begingroup\$ Determining whether the greedy algorithm works for a specific set of denominations was first answered in Magazine, Nemhauser, and Trotter in 1975. This cs.stackexchange addresses the topic. \$\endgroup\$ – Llaves Sep 22 '16 at 5:03
4
\$\begingroup\$

Algorithm

Your algorithm is O(m): for very large values of m, you'll execute the change++ statement \$\lfloor \frac{m}{10} \rfloor\$ times (plus up to 5 more times, if m ends in 9, but that hardly matters).

A good algorithm would be O(1) — constant time:

return (m / 10) +                // count of 10's
       (m % 10 >= 5 ? 1 : 0) +   // count of 5's
       (m % 5);                  // count of 1's

(I wouldn't bother looping or generalizing, since that technique only works for well designed sets of denominations. With denominations {10, 4, 3, 1}, for example, you would need an entirely different algorithm based on .)

Presentation

  • Wildcard imports should generally be avoided. In this case, all three of your import statements were completely unnecessary.
  • /* Name of the class has to be "Main" only if the class is public. */

    That comment makes no sense at all. The visibility of the class has no bearing on what you should name it. ChangeMaker might be a good name for the class.

  • Your indentation, spaces, and braces are inconsistent:

      public static int CountChange(int m) {
    

    vs.

        public static void main (String[] args) throws java.lang.Exception
        {
    
  • CountChange violates Java naming conventions: it should be countChange.
  • throws java.lang.Exception is superfluous, since uncaught exceptions will naturally lead to aborting with a stack trace. What exceptions are you expecting, anyway?
  • In int[] denomenations = new int[]{10, 5, 1};, "denominations" is misspelled. I would also add a comment to warn that the algorithm does not work with arbitrary sets of denominations.
  • The if (m <= 0) return 0; special case is unnecessary: the function would return exactly the same results without it. I would eliminate that check, to reduce the possible codepaths.
\$\endgroup\$
  • \$\begingroup\$ For guard clause as I said I knew that my algorithm works for m=0 but for readability I put the condition up there and that was my question if that is a good convention or not. \$\endgroup\$ – CodeYogi Sep 22 '16 at 2:37
  • \$\begingroup\$ Second thing, your solution is too tied to the example I was expecting some generic solution and as the question says suppose I did this during the interview what would be the reaction of the interviewer? \$\endgroup\$ – CodeYogi Sep 22 '16 at 2:39
  • \$\begingroup\$ I believe I've already stated my reasoning for both recommendations. If the general case works, then the redundant special case just adds clutter. (A special case might be justified if it could lead to a faster answer, but that's not the case here.) Also, generalizing this greedy algorithm is counterproductive, since it only works with specific sets of denominations. To any interviewer who objects, my response would be: "YAGNI", followed with an offer to write a fully general dynamic programming solution. \$\endgroup\$ – 200_success Sep 22 '16 at 3:43
7
\$\begingroup\$

I think that a better algorithm can be developed and suggestions are welcome.

Yes! The core of the algorithm is the following:

for (int i : denomenations) {
  while (m - i >= 0) {
    m -= i;
    change++;
  }
}

What this does is looping through all the possibles denominations in descending order, removing them as long as necessary. This is the right idea: for a given number, like 36, this subtracts 10 three times, then 5 one time and then 1 one time.

This can be done in a faster way. You know in advance how many times you will need to loop. It is precisely m / i (with an explicit integer division).

  1. Given 36, you want to know how many times 10 fits in there. This is the quotient of the integer division of 36 by 10, which is 3, result of 36 / 10.
  2. Then, what remains in m is the remainder of the integer division of 36 by 10, which is 6, result of 36 % 10.

As such, you can have:

for (int i : denomenations) {
    change += m / i;
    m %= i;
}

without a single inner while loop.

I am not so sure about the initial time complexity of the algorithm, but with this revision, you clearly have a linear algorithm in terms of the denominations, which is probably the same as the original but will effectively be faster.

I put some thoughts on testing strategies in this problem, since the input is integer I had few number of edge cases also the problem description doesn't cover edge cases (eg: maximum integer) but then also I thought to test it, is this the correct approach?

Testing edge cases is always welcomed, and I would encourage it. Do note that unit tests should typically sit in a dedicated test class run with a testing framework, like JUnit for example.

For m = 0 the algorithm works fine but still I gave a guard condition for readability, don't know if this is a good strategy.

This is perfectly fine. You have an early return for negative values so you can add 0 to it since the results would already be known in advance.


A couple of other comments:

  • Beware of typos: denomenations should be denominations.
  • Since they are constants, you might also want to turn them explicitly into constants. A better alternative would be to let the CountChange method take the array of denomination as argument; this way, it is completely independant of actual values.
  • The method name should be countChange, not CountChange, with regard to Java naming conventions.
  • Consider having more descriptive names than m and i. One letter variables can be fine if their scope is really tight, but here, a longer name would be appropriate.
\$\endgroup\$
  • 1
    \$\begingroup\$ Works if no coin worth more than half next most valuable coin. Might fail otherwise. Add a 6 coin. Make 12 with this algorithm = 10 +1+1, not 6+6 \$\endgroup\$ – innisfree Sep 21 '16 at 22:12
  • \$\begingroup\$ @innisfree: Try making change for 27 with coins of size 20, 9, and 1, and you'll see that that requirement isn't enough either. \$\endgroup\$ – user2357112 Sep 21 '16 at 22:23
  • 1
    \$\begingroup\$ Those are very good points, the prerequisite here that the next coin is a multiple of the one before so it works in this particular case. I believe there are more cases where it would work but, yes, it's definitely not a general purpose solution, which would more complicated. \$\endgroup\$ – Tunaki Sep 21 '16 at 22:42
  • \$\begingroup\$ @user2357112 oops yes, hmm what is the general requirement? \$\endgroup\$ – innisfree Sep 22 '16 at 0:15
  • 1
    \$\begingroup\$ @CodeYogi No but the problem statement is about those specific denominations, for which your algorithm (called the greedy algorithm) works. Asked this way, I don't think the question wants a general purpose algorithm (and even if the greedy algorithm doesn't give the right answer, it's still a solution); in an interview, having this simple solution and mentioning that a dynamic programming one would always work is enough IMO. \$\endgroup\$ – Tunaki Sep 22 '16 at 9:55
2
\$\begingroup\$

Question 1

Assuming that integer division runs in \$\mathcal{O}(1)\$, you can compute the minimum coin amount in time \$\Theta(D)\$, where \$D\$ is the number of denominators (in your case, \$D = 3\$).

Question 3

In algorithms, the aim is usually to maintain invariants that will preserve correctness. If it works for m = 0 (or even negative m), leave it without the check. (However, it is crucial to understand why it works if it works.) Some algorithms does not work correctly with some input, so special treatment of such input might be in order.

Question 4

Returning to the first question, try this:

public static int countChangeV2(int m) {
    if (m <= 0) {
        return 0;
    }

    int coins = 0;

    for (int i : new int[]{ 10, 5, 1 }) {
        int localCoins = m / i;
        coins += localCoins;
        m -= localCoins * i;
    }

    return coins;
}

Hope that helps.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.