Coin Change Problem: Dynamic Programming

package com.hackerrank.problems;

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class CoinChange {

    static long getWays(long n, long[] c){

        // Complete this function

        Map<String,Long> m =  new HashMap<>();

        

        return change(n, c, 0, m);

    }

    

    static long change(long n, long[] c, int index, Map<String, Long> map){

        

        if(n == 0){

            return 1;

        }

        

        if(index >= c.length){

            return 0;

        }

        

        long ways = 0;

        

        long amountWithCoin = 0;

        

        String key = n + "-" + index; 

        System.out.println("Key" + key);

        

        if(map.containsKey(key)){

            return map.get(key);

        }

        

      

        while(amountWithCoin <= n){

            long remaining = n - amountWithCoin;

            ways = ways + change(remaining, c,index+1,map);

            amountWithCoin = amountWithCoin + c[index];

            System.out.println("Amount With Coin" + amountWithCoin);

        }

        map.put(key, ways);

        return ways;

    }

    public static void main(String[] args) {

        

        int n = 35;

        

        long[] c = {2, 5, 3, 6};

        

        long ways = getWays(n, c);

        

        System.out.println(ways);

    }

}

HashSet vs LinkedHashSet

**HashSet** uses buckets to store data which is stored in the form of array.

**LinkedHashSet** uses *doubly linked list* internally to store the data.

Now when the iteration happens in the HashSet the time depends on the `capacity` of the `HashSet`.

In case of LinkedHashSet it depends on the number of elements present in the set.

So even if the number of elements are lesser in the HashSet it might take more time because of the buckets. Hence iteration in LinkedHashSet is faster than HashSet.

From [grepcode][1]:

> Performance is likely to be just slightly below that of HashSet, due
> to the added expense of maintaining the linked list, with one
> exception: Iteration over a `LinkedHashSet` requires time proportional
> to the size of the set, regardless of its capacity.  
> Iteration over a HashSet is likely to be more expensive, requiring time proportional to
> its capacity. A **linked hash set** has two parameters that affect its
> performance: *initial capacity and load factor*. They are defined
> precisely as for `HashSet`. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashSet, as iteration times for this class are
> unaffected by capacity.


  [1]: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b27/java/util/LinkedHashSet.java/