Give me some change as asked in interview

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.

Algorithm

Your algorithm is O(m): for very large values of m, you’ll execute the change++ statement ⌊m10⌋

$\lfloor \frac{m}{10}\rfloor$

$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 dynamic-programming.)

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.

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.

Question 1

Assuming that integer division runs in O(1)

$\mathcal{O}(1)$

$mathcal{O}(1)$, you can compute the minimum coin amount in time Θ(D)

$\mathrm{\Theta }(D)$

$Theta(D)$, where D

$D$

$D$ is the number of denominators (in your case, D=3

$D=3$

$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.