Ilya Gazman
BAN USERIt's not the best thing, but it gave me the answer 2200
public class ChangeOf78 {
public static void main(String[] args) {
new Go();
}
private static class Go{
private final Coin coin25 = new Coin(25, 2);
private final Coin coin10 = new Coin(10, 3);
private final Coin coin5 = new Coin(5, 5);
private final Coin coin1 = new Coin(1, 7);
private HashMap<Integer, ArrayList<Coin>> coinsMap = new HashMap<>();
public Go(){
calculateChange(new ArrayList<Coin>(), 25);
System.out.println(Math.pow(coinsMap.size(), 3) + 3);
}
private void calculateChange(ArrayList<Coin> coins, int sum){
if(sum == 0){
int key = 1;
for (Coin coin : coins) {
key *= coin.id;
}
coinsMap.put(key, coins);
return;
}
if(sum >= 25){
add(coins, sum, coin25);
}
if(sum >= 10){
add(coins, sum, coin10);
}
if(sum >= 5){
add(coins, sum, coin5);
}
if(sum >= 1){
add(coins, sum, coin1);
}
}
@SuppressWarnings("unchecked")
private void add(ArrayList<Coin> coins, int sum, Coin coin) {
coins = (ArrayList<Coin>) coins.clone();
coins.add(coin.clone());
calculateChange(coins, sum - coin.value);
}
private class Coin{
int id;
int value;
public Coin(int value, int id) {
this.id = id;
this.value = value;
}
@Override
public Coin clone() {
return new Coin(value, id);
}
@Override
public String toString() {
return value + "";
}
}
}
}
RepLisaBAllen, Accountant at ABC TECH SUPPORT
I am Lisa a certified Personal Trainer with more than 7 years experience in the local and international fitness scene ...
Repalinehchavez, SHOT 1500 NIGHT 5000 Call girls in Munirka Metro 9711794795 at Apple
Hi, I am Aline From New York USA. I am working as a Real estate rental agent in an Energy ...
RepRuthOrvis, AT&T Customer service email at 8x8
Hey I am Ruth Working as a branch manager in a bank.I have worked here for the last 4 ...
In the worse case, you need to output the entire array. I am not assuming that I have enough disk space to do so, so let's say I will be outputting to some output stream, it can be the disk or some external service.
- Ilya Gazman January 28, 2019In the words case, all the triples matches will appear at the end of the array, so I will have to keep a track on all the numbers at the beginning of the array. I am not assuming that I can put 2/3 of the array in memory so I will store the data in a database, that is not necessary on my machine.
Having said that memory can be optimized by encoding the data, let's say into ranges or using in-memory zip stream, but even with all those optimizations I wouldn't assume that I have enough memory.