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 &quot;Main&quot; only if the class is public. */
class Main
{
  
  public static int CountChange(int m) {
    if (m &lt;= 0) return 0;
    
    int[] denomenations = new int[]{10, 5, 1};
    int change = 0; 
    
    for (int i : denomenations) {
      while (m - i &gt;= 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

This seems exponential algorithm to me but what is the correct approach for finding the running time of this algorithm?
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?
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.
I think that a better algorithm can be developed and suggestions are welcome.
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 &gt;= 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).


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