How to save values to an array?

You are given an array A of k values which contain int values in sorted (asec) order. Find top k values (asec) which can either be the number from the array A, or sum of any two numbers from A or sum of any three numbers from A.?

• So, if A's values are represented as : a1,a2,...,ak , the possible numbers can be: a(i), a(i)+a(j), a(i)+a(j)+a(l) for any i,j,l < k Ex: A[7] = {3,4,5,15,19,20,25} output B[7] = {3,4,5,(3+4),(3+5),(4+5),(3+4+5)} case a: when B[] need not be sorted case b: when B[] needs to be sorted

• Answer:

  Explanation: The solution to this problem is going to be a lot like the merge operation of merge sort.  What that means is that we will have a set of sorted lists that we want to merge.  We will select the smallest elements from those lists until we have k elements.  That will be our solution. So first, what are the lists we need to merge?  We need the smallest of: The original list of numbers in ascending order The list produced by all 2-element combinations of the original list in ascending order The list produced by all 3-element combinations of the original list in ascending order We already have the first list, so we just need to generate the second and third lists.  The naive approach would be to generate all values in lists 2 and 3 and then to sort the values.  However, we might be able to do better than that.  If we think about the merge operation we are doing, we really need to get only the smallest element of each list per iteration.  Whenever we select the smallest element, we then need to get the next smallest element.  Maybe we can make a function to get successive values from list 2 and list 3 in constant time. If that were possible, however, then we could generate a sorted list of all pairwise sums in [math]\Theta(n^2)[/math] time.  The best known solution for generating all pairwise sums of a list in sorted order is [math]\Theta(n^2 \lg n)[/math] (see http://cs.smith.edu/~orourke/TOPP/P41.html#f-hgiit-76.  If you think of a way to do it, let me know! :)  For the purposes of an interview, I don't expect you to invent breakthroughs in computer science.  Therefore, we'll go with the naive [math]\Theta(n^2 \lg n)[/math] solution, which is to generate all pairs and then to sort each pair by its sum.  We can generate all pairs in [math]\Theta(n^2)[/math] time, and we can sort them in [math]\Theta(n^2 \lg n)[/math] time (since [math]n^2 \lg n^2[/math] is the same as [math]2 n^2 \lg n[/math]), giving us our sorted list of pairwise sums in [math]\Theta(n^2 \lg n)[/math] time.  Similarly, we can generate a sorted list of all 3-element sums in [math]\Theta(n^3 \lg n)[/math] time. Given lists 1, 2, and 3, we can repeatedly select the minimum element from lists 1, 2, or 3 until we have [math]k[/math] elements.  The [math]k[/math] elements that we select will be our solution. The overall run-time of this solution is [math]\Theta(n^3 \lg n)[/math] (assuming [math]k[/math] can't be greater than the size of the concatenation of lists 1, 2, and 3, which is a reasonable assumption given that we want to have actual values to return). Notes: My solution solves case (b) from your problem statement.  Therefore, it also solves case (a).  I can't think of a more efficient way to solve the problem if I need to satisfy only case (a)--at least in terms of asymptotic complexity. While the solution described above is the best asymptotic solution I can think of, that does not mean that there are not more efficient solutions.  However, any other solution will still have the same asymptotic run-time (unless a better solution to the open problem I mentioned above is devised). Let's think about what a more efficient solution might look like.  Suppose [math]k[/math] is small enough that we know we won't need to generate lists 1, 2, or 3 in their entirety.  Then we could truncate those lists as necessary to save execution time Truncating list 1 is trivial.  Truncating lists 2 and 3 and keeping them sorted is a little more difficult.  One possible solution I pose would be to do something similar to binary search.  For example, suppose we only want the 5 smallest elements of list 2.  We could start with two pointers into list 1, one at index 0 and one at index 1.  We could then increment one pointer by 1 and decrement the other pointer by as many elements as possible such that the sum of the values pointed to by the two pointers does not go below the previous sum.  (We can find out how many elements by which to decrement the other pointer with a modified binary search).  Thus, we can find each successive element in list 2 in [math]\Omega(\lg n)[/math] time.   However, we have to be careful if we want to avoid having the pointers move in cycles.  This method still has a run-time of [math]\Theta(n^2 \lg n)[/math] if we use it to generate all [math]n^2[/math] pairwise sums, but it has the added benefit that we can grab the smallest element one step at a time.  If we only need a few elements from lists 2 and 3, a method like the one I just described might be more ideal.   Java Implementation: import java.util.Arrays; public class KSmallestWithCombosOf2And3 { public static void main(String[] args) { int[] A = { 3, 4, 5, 15, 19, 20, 25 }; Integer[] B = KSmallestWithCombosOf2And3(A, 63); System.out.print("[ "); for (int i = 0; i < B.length; i++) { String next = (i == B.length - 1) ? " " : ", "; System.out.print(B[i] + next); } System.out.println("]"); } public static Integer[] KSmallestWithCombosOf2And3(int[] list, int k) { if (k < 1 || list == null || list.length == 0) { return new Integer[0]; } Integer[] result = new Integer[k]; int[][] lists = new int[][] { list, getCombosOf2(list), getCombosOf3(list) }; int[] ptrs = { 0, 0, 0 }; for (int i = 0; i < k; i++) { int min = 0; int minIndex = 0; boolean minAssigned = false; for (int j = 0; j < 3; j++) { if (ptrs[j] < lists[j].length && (lists[j][ptrs[j]] < min || !minAssigned)) { min = lists[j][ptrs[j]]; minIndex = j; minAssigned = true; } } if (minAssigned) { ptrs[minIndex]++; result[i] = min; } else { result[i] = null; } } return result; } public static int[] getCombosOf2(int[] list) { int n = list.length; int numCombos = n * (n - 1) / 2; int[] result = new int[numCombos]; for (int i = 0, c = 0; i < n; i++) { for (int j = 0; j < i; j++, c++) { result[c] = list[i] + list[j]; } } Arrays.sort(result); return result; } public static int[] getCombosOf3(int[] list) { int n = list.length; int numCombos = n * (n - 1) * (n - 2) / 6; int[] result = new int[numCombos]; for (int i = 0, c = 0; i < n; i++) { for (int j = 0; j < i; j++) { for (int k = 0; k < j; k++, c++) { result[c] = list[i] + list[j] + list[k]; } } } Arrays.sort(result); return result; } } Output: [ 3, 4, 5, 7, 8, 9, 12, 15, 18, 19, 19, 20, 20, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 26, 27, 27, 28, 28, 28, 29, 29, 30, 32, 33, 34, 34, 35, 37, 38, 38, 39, 39, 39, 40, 40, 42, 43, 43, 44, 44, 44, 45, 45, 47, 48, 48, 49, 49, 50, 54, 59, 60, 64 ]