Skip to content

Instantly share code, notes, and snippets.

@lucasheriques
Created June 10, 2017 01:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lucasheriques/55dfb151e0d04e61820888bf7c1f9f83 to your computer and use it in GitHub Desktop.
Save lucasheriques/55dfb151e0d04e61820888bf7c1f9f83 to your computer and use it in GitHub Desktop.
CoinCollector algorithm
package com.company;
import java.io.*;
import java.util.Arrays;
/**
* Created by lucashenrique on 03/06/17.
*/
public class Main {
public static int coinCollector(int[] coins) {
int n = 1;
int currentValue = coins[0];
for (int i = 1; i < coins.length; i++) {
if (i < coins.length - 1 && currentValue + coins[i] < coins[i+1]) {
currentValue += coins[i];
n++;
}
else if (currentValue < coins[i] && i == coins.length - 1)
n++;
}
return n;
}
public static void readCoin() throws IOException {
BufferedReader d = new BufferedReader(new InputStreamReader(System.in));
String ler = null;
ler = d.readLine();
int casos = Integer.parseInt(ler);
while (casos > 0) {
ler = d.readLine();
int nMoedas = Integer.parseInt(ler);
ler = d.readLine();
int[] moedas = new int[nMoedas];
for (int i = 0; i < nMoedas; i++) {
moedas[i] = Integer.parseInt(ler.split(" ")[i]);
}
Arrays.sort(moedas);
casos--;
System.out.println("Número máximo de moedas: " + coinCollector(moedas));
}
d.close();
}
public static void main(String[] args) throws IOException {
readCoin();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment