Find amounts that cannot be composed using the given coins I need to make a program that receives a set of currencies and tests which values between 1 and 10,000 units can not be produced with these currencies.

The program must have 2 input data:


  
  The number n of existing coin values, with n between 1 and 10.
  The values a1, a2, ..., an of these currencies.
  


The program should read this data and determine how many values between 1 and 10000 currency units can not be achieved using these currencies.

For example, if we wanted to provide the data on some existing currencies we would have the following entry:


  1
  
  5
  
  10
  
  25
  
  50
  
  100


Of course, since this system supplies one cent, all values ​​can be obtained.

I would like to know how I can improve the performance of my code or some part that is poorly written.

import java.sql.Date;
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;
import java.util.Vector;

public class CoinChallange {

    private static int [] coins = {5, 11, 13, 23, 29};
    private static int [] numbers;
    private static int [] quantity = { 0, 0, 0, 0, 0};
    private static int i, n, a, b, c, d, e, sum;

    public static void main(String[] args) 
    { 

        long start = System.currentTimeMillis();  

        numbers = new int[10001]; 
        i = 0;

        for (n = 0; n &lt;= 10000; n++) {      
            numbers[n] = n;
        }

        for ( quantity[0] = 0; quantity[ 0 ] &lt;= 2000; quantity[0]++ ) {
            for ( quantity[1] = 0; quantity[ 1 ] &lt;= 2000; quantity[1]++ ) {
                for ( quantity[2] = 0; quantity[ 2 ] &lt;= 2000; quantity[2]++ ) {
                    for ( quantity[3] = 0; quantity[ 3 ] &lt;= 2000; quantity[3]++ ) {
                        for ( quantity[4] = 0; quantity[ 4 ] &lt;= 2000; quantity[4]++ ) {
                            System.out.println( " " + quantity[0] + " " + quantity[1] + " " + quantity[2] + " " + quantity[3] + " " + quantity[4] );
                            sum = quantity[0]*coins[0]+
                                   quantity[1]*coins[1]+    
                                   quantity[2]*coins[2]+    
                                   quantity[3]*coins[3]+    
                                   quantity[4]*coins[4];
                            if ( sum &lt;= 10000 ) {
                                numbers[ sum ] = -1; 
                            }
                        }
                    }
                }
            }
        }

        for (n = 1; n &lt;= 10000; n++) {
            if ( numbers[n] &gt; 0 ) {
                System.out.println( numbers[n] );
            }
        }

        long end  = System.currentTimeMillis();   
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(end - start)));  

    }

}


I get to the right result, but it is taking a long time, I believe my logic is very bad.
Your code looks frighteningly slow because of the 5 nested for loops, and indeed it is.

To find an efficient algorithm, you should switch off the computer, take out a sheet of paper and solve the following task on paper:


  Given an infinite amount of coins labelled 5, 7, 16, which amounts between 1 and 100 can be composed?


While you solve that task, ask yourself in every step:


what am I doing?
why do I do this?
what do I want to achieve?
can I formulate a general rule for this that sounds reasonable, appropriate for the task?


Your current code counts up to 2000 several times. In this manual task there is no point counting up to 2000. This alone makes your algorithm more specialized than it needs to.

Essentially your code should be defined in a function like this:

/**
 * @return the amounts between min and max that are &lt;i&gt;not&lt;/i&gt; composable
 * from an infinite supply of coins of the given values.
 */
public static BitSet uncomposable(int min, int max, List&lt;Integer&gt; coinValues) {
    …
}


In that code, neither the number 100 nor 10000 nor 2000 must appear.
There should be at most 2 nested loops.
How exactly the code looks like depends on how you solved the task on paper.
I'm sure you won't choose a time-consuming algorithm when having to do this task manually.

Bonus question: is there a limit beyond which all amounts are composable? That could be used to stop the computation early, which is a nice optimization. Try with these test cases:


{1}: the limit is 0, obviously
{2}: there's no limit since only even numbers are covered
{2, 4, 6}: …
{3, 5}: …
{1, 7, 14}: …