@@ -0,0 +1,1858 @@
+package com.sunny.grokkingalgorithms.fasttrack.week2;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.HashSet;%0Aimport java.util.List;%0Aimport java.util.Set;%0A%0A/**%0A * Created by sundas on 6/24/2018.%0A */%0Apublic class KNumbersInAnArrayThatAddToC %7B%0A%0A  /*%0A  K numbers in array that sum to C%0A  In general, when k is even, we have the following algorithm:%0A%0ACompute a set S that stores all the sums of all the k/2-element tuples of the original array%0ALook at every k/2 tuple of elements in the original array, and compute its sum s. If C?s?S, we found a solution%0AThis is O(nk2)%0A%0AWhen k is odd, we have the following algorithm:%0A%0ACompute a set S that stores all the sums of all the (k?1)/2-element tuples of the original array.%0ALook at every (k+1)/2-element tuple in the original array, and compute its sum s. If C?s, we found a solution.%0AThis is O(nk+12)%0A%0AWe have VMs of sizes 6, 9, 20. How do we determine whether we can provide VM's clients requirement.%0AEx 35 (20+9+6) or 18%0A(6+6+6 or 9+9)%0A%0A   */%0A%0A  /**%0A   *%0A   * @return%0A   */%0A  public static Set%3CSet%3CInteger%3E%3E getPlacement(int%5B%5D vms,int k)%7B%0A    Set%3CSet%3CInteger%3E%3E placements = new HashSet%3C%3E();%0A    Set%3CInteger%3E holder = new HashSet%3C%3E();%0A    for(int i = 0 ; i %3C vms.length ; i++)%7B%0A      holder.add(vms%5Bi%5D);%0A    %7D%0A    for(int i = 0 ; i %3C vms.length ; i++)%7B%0A      for(int j = i ; j %3C vms.length ;j++)%7B%0A        int s = vms%5Bi%5D + vms%5Bj%5D;%0A        if(holder.contains(k - s))%7B%0A          Set%3CInteger%3E placement = new HashSet%3C%3E();%0A          placement.add(vms%5Bi%5D);%0A          placement.add(vms%5Bj%5D);%0A          placement.add(k - s);%0A          placements.add(placement);%0A        %7D%0A      %7D%0A    %7D%0A    return placements;%0A  %7D%0A%0A  /**%0A   *%0A   * @param args%0A   */%0A  public static void main(String%5B%5D args) %7B%0A    int%5B%5D vms = new int%5B%5D%7B6,9,20%7D;%0A    System.out.println(getPlacement(vms,35));%0A    System.out.println(getPlacement(vms,18));%0A  %7D%0A%0A%7D%0A

Finding k number s that add to c. O(n.pow(k+1/2))