Troquinhos.java

import java.sql.Date;
import java.text.SimpleDateFormat;
import java.util.*;

public class Troquinhos {
 
	public static int Intervalo = 100;
	
	public static void main(String[] args) {		
		long inicio = System.currentTimeMillis();  
		
		int[] moedas = new int[] { 3,7,11 };
		int dictLength = Intervalo / 2;		

		ArrayList<Integer> numeros = new ArrayList<Integer>();
		ArrayList<Integer> invalidos = new ArrayList<Integer>();

		for (int i = 1; i < Intervalo; i++) {
			int moeda = moedas[0];
			int v = moeda * i;
			if (v > dictLength) {
				break;
			}
			numeros.add(v);
		}

		for (int i = 1; i < moedas.length; i++) {
			int moeda = moedas[i];
			numeros.add(moeda);
			int size = numeros.size();

			for (int j = 0; j < size; j++) {
				int v = moeda + numeros.get(j);
				if (v > dictLength) {
					break;
				}
				numeros.add(v);
			}
		}

		numeros = mergeSort(numeros);
		System.out.println(numeros);

		int temp = 0;
		for (int i = 0; i < numeros.size() - 1; i++) {
			int first = numeros.get(i);
			int second = numeros.get(i + 1);
			if (first == second - 1) {
				temp++;
				if (temp > 10) {
					temp = first;
					break;
				}
			} else {
				temp = 0;
			}
		}

		System.out.println("LOG => " + temp);

		Boolean has = temp > 10;
		int indexN = 0;
		for (int i = 1; i < Intervalo; i++) {
			if (has && i >= temp) {
				break;
			} else if (i == numeros.get(indexN)) {
				indexN++;
				continue;
			}
			invalidos.add(i);
		}

		System.out.println("Invalidos => " + invalidos);

		long fim  = System.currentTimeMillis();   
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(fim - inicio)));  
	}

	public static ArrayList<Integer> mergeSort(ArrayList<Integer> a) {
		if (a.size() <= 1) {
			return a;
		}
		ArrayList<Integer> firstHalf = new ArrayList<>();
		ArrayList<Integer> secondHalf = new ArrayList<>();
		for (int i = 0; i < a.size() / 2; i++) {
			firstHalf.add(a.get(i));
		}
		for (int i = a.size() / 2; i < a.size(); i++) {
			secondHalf.add(a.get(i));
		}
		return merge(mergeSort(firstHalf), mergeSort(secondHalf));
	}

	public static ArrayList<Integer> merge(ArrayList<Integer> l1, ArrayList<Integer> l2) {
		if (l1.size() == 0) {
			return l2;
		}
		if (l2.size() == 0) {
			return l1;
		}
		ArrayList<Integer> result = new ArrayList<>();
		int nextElement;
		if (l1.get(0) > l2.get(0)) {
			nextElement = l2.get(0);
			l2.remove(0);
		} else {
			nextElement = l1.get(0);
			l1.remove(0);
		}
		result.add(nextElement);
		result.addAll(merge(l1,l2));
		return result;
	}
	
}