CareerCup

1. Sort both arrays in descending order

/* Insert A[0] + B[0] into max heap */
   max_heap.put(0, 0, A[0]+B[0]);
   while (--k) {
       p = max_heap.get();

       if (p.a_index < p.b_index) {
           sum = A[p.a_index] + B[p.b_index+1];
           max_heap.put(make_pair(p.a_index, p.b_index+1, sum));
       } else if (p.a_index > p.b_index) {
           sum = A[p.a_index+1] + B[p.b_index];
           max_heap.put(make_pair(p.a_index+1, p.b_index, sum));
       } else { /* add both adjacent elements */
           sum = A[p.a_index] + B[p.b_index+1];
           max_heap.put(make_pair(p.a_index, p.b_index+1, sum));
           sum = A[p.a_index+1] + B[p.b_index];
           max_heap.put(make_pair(p.a_index+1, p.b_index, sum));
       } 
   }

    p = max_hep.get();
    sum = A[p.a_index] + B[p.b_index];
    printf("kth max sum is formed by A[%d] + B[%d] = %d\n", p.a_index, p.b_index, sum);

can you please rephrase the question? It's not understandable.
thanks

Is it Kth sum of 2 elements where each elements are picking from both arrays?

If i got it correctly then there will be two arrays sorted/unsorted now we need to find out sum of elements which will be kth largest....
If this is right(if unsorted) u might want to sort it and start adding from the end...u know every (i)mod3 th largest sum as A[n]+B[n] is the largest then we've A[n]+B[n-1],A[n-1]+B[n] in between..next 4th biggie is A[n-1]+B[n-1]...go something this way...u already ....but this will not be the question I am sure this one's so darn easy....

I am hoping this will be more like subset sum up to kth largest in two unsorted arrays :D ....

Sort both the arrays in descending order O(nlogn) and then the following code snippet

int Kthlargepair(int[] a, int[] b)
{
int aIndex = 0;
int bIndex = 0;
for(int i = 1; i < k; ++i)
{
if(a[aIndex] > b[bIndex])
++aIndex;
else
++bIndex;
}
return a[aIndex] + b[bIndex];
}

The above code is of complexity O(n)

Total complexity: O(nlogn)+O(n) = O(nlogn)

What I can think is of O(n^2)

Maintain a mean heap of size k.For each sum(one element from first array and another from second array),if sum<top_of_the_heap the no need to insert it
else
Remove the top.Insert the sum at the top.Call Min heapify.
At last the top element is the kth largest.

This problem can solved in O(n * log(max_Value(a) + max_Value(b) )) + O(nlogn) using binary search. First sort both the arrays. Now consider the following query .
How many pairs of numbers are there which have sum >= to the given value. This query can be solved in many ways . There are two algorithms to solve this query . The first one in the best case takes O(logn) and worst case O(nlogn).Another algorithm takes always O(n) time. Once you can answer this query we can use binary search to solve the given problem.

int search(int start, int end,const int &K) {
if(start>end)
return -INF;
int mid = (start+end)>>1;
//func(arg) returns how many pairs are there which have sum >=arg
int no_pairs = func(mid);
if( no_pairs < K ) {
return search(start,mid-1,K);
}
else if( no_pairs > K ) {
return search(mid+1,end,K);
}
else{
return max(mid, search(mid+1,end,K) ) ;
}
}

Working of the above algorithm:
First of all we note that kth maximum is a number b/w min_value(a)+min_value(b) and max_value(a)+max_value(b) . So we do a search in this interval for that kth maximum. By definition kth maximum sum means a value in the sum array and number of elements in that sum array greater than this value is k-1.
Algorithm working: If the number of pairs which have sum>=mid is say Count. if Count
> K then we search in [mid+1,end] . If Count < K then we search in [start,mid-1] . Now if Count ==K then we note that the value mid can be our answer or there can be another integer larger than this and for which Count==K . Suppose your sum array is 1 2 10 15. and K is 2 . Then 3,4,5,...10 values satisfy the condition that number of pairs greater than that value is 2. Now convince yourselves that the answer is maximum among all the values.


It is good exercise to think how we can write the function by name func used in this binary search :)

Sort Both Arrays complexity O(nlogn)
e.g.
a1[] = {10 9 6 4 2}
a2[] = {11 9 7 1}

Create another result array r[] sorted using insertion sort & count number of elements in result array

1st Pass:
take 1st element of a1 & a2 sum = 21 insert r[1] (count = 1)

check if k <= count (every time when pass over)
a1[0]+a2[0] = 21
take a1[0]+a2[1] = 19 compare a2[0]+a1[1]=20 (inset 20) r2 = [20] count 2
check if k <= count (every time when pass over)

a2[1]+a1[1] = 18 < 19
insert 19 r3 = 19
check if k <= count (every time when pass over)

compare element is 18 now
now traverse on a1 with each a2 element upto index 1 in above line
a1[0]+a2[0] already there
a1[0]+a2[1] = 19 already checked
a1[1]+a2[0] there
a1[1]+a2[1] =18 checking element
a1[2]+a2[0] = 17 < 18

inser 18 count 4 r4[] =18
check if k <= count (every time when pass over)

so on........

r[] = {21, 20 , 19, 18, 17...}
sorted
kth element is there

kth largest sum from two arrays. sum of how many elements? two? if so, are they one from each array? or the could be from array?
"Question Unclear"

Rahul has the best answer

1)Sort both array (nlogn)
2)now we have A[n] and B[m] two sorted array.
take iA and iB two index variable
lets create a minimum heap minHeap(max size=k);
n+

for each iA+iB=0 Add A[iA]+A[iB](only one elem in heap till now)
for each iA+iB=1 Add A[iA]+A[iB](only 2 more elem in heap added)
.....
do the same thing till you are able to add elemment in k space heap
suppose
for each iA+iB=x Add A[iA]+A[iB](no element found space in k spaced heap)

after this point every element formed will be lesser than found in last iteration

here minimum value of heap will be the kth element.

ps: the idea is to create virtual young's table and iterate thru each diagonal,till one diagonal miss entry in minheap

Complexity of step 2 will be about K(logK).

Total complexity = nlogn +nlogn + klogk =O(nlogn)

The easies solution i hope...
1) Sort both arrays A[] and B[]
2) result = 0;
for each b in B {
result += countElementsThatAreLessThan(k - b);
}

Where countElementsThatAreLessThan is simple binary search function that finds index of last element in A that is less than given value;

O(nlogn)

I have an idea:
1. sort both A[] and B[];
2. do something like merging them:
a)find p that A[0]->A[p-1]>B[0] and A[p] < B[0];
now we have the biggest (p) elements in both A and B (they are from A);
b)find q that B[0]->B[q-1]>A[p] and B[q] < A[p];
now we have the second biggest (q) elements in both A and B (they are from B);
so these two sets of elements will make the (p*q) biggest SUMs.
3.if(k > p*q),we will do the same to find (k-q*q)th max sum in A[p..n] and B[0..n]
4.if(k < p*q),we could find it in A[0..p-1] and B[0..q-1].They are both sorted and A[p-1] > B[0].In this case, A[0] and B[0] will be make the biggest sum, and A[0..1] and B[0..1] will make the biggest 2*2 sums, and A[0..2] and B[0..2] will make the biggest 3*3...so we can get the position X that X >=sqrt(k) and X <= sqrt(k)+1. (A[X] and B[0..X]) and (B[X] and A[0..X]) will make the (X-1)^2+1 to X^ biggest sums,we can really sort them now

1) Sort both arrays in descending order. O(nlogn)
2) Merger them in descending order O(n)
3) Find biggest n such n*(n-1)/2 is < k. O(?) probably sqrt of 2k+1.
4) add n+1 the element to mergedArray(k- nC2) O(constat)

final order O(n).

Any gotcha in logic?

Sorry, final order in above methos id O(nlogn).
Basically 2 elements can be picked from n numbers in nC2 ways.
if we find max n such nC2 is less than K, any combinational sum of those n numbers is bigger than kth sum. then we pick n+1 elemtn and keep adding from highest number to get nC2+1th number etc.

I don't think there is a sure way to avoid the case that Rahul's algorithm missed. How about the following:
1) Order the two arrays a and b in descending order
2) Starting with a[i] where i=0, add it to b[j] where j = 0 ... n and b[j] > a[i+1] and store the values to a result array, using insertion sort
3) Increment i and repeat (the last element of a will obviously be a special case since there is no i+1)
4) This way, at each "round", the largest number in that round is strictly smaller than the largest number in the previous round so to find kth largest sum, we only need to compute while i < k.

I might be missing something though. Any thoughts?

Sort the array first then do the following

int KthlargestSum(int[] a, int[] b)
{
int aIndex = 0;
int bIndex = 0;
Sum = 0;
for(int i = 1; i < k; ++i)
{
    if(a[aIndex] > b[bIndex])
    {
           sum + = a[aIndex]
           ++aIndex;
    }
    else
   {
         sum + = a[bIndex]
      ++bIndex;
    }
}
return sum;
}

Time O(nlogn) + O(k) = O(nlogn)
Space O(1)

I don't know why so many people wasting their time on this bullshit question.

If you are posting a question, please explain it well.

What an unclear and idiot question is this?

This is an instance of a top-k problem. Take a look at TA, NRA algorithm. With the objective function here is x+y where x, y are two attributes of a database.

here's my solution in (nlgn+k) time.

Sort the both arrays.
Start from the end.
Let the arrays be A and B.
at each step maintain two pointer to last element of arrays.

At each point, compare A[last1]+ A[last1-1] , B[last2]+ B[last2-1] and A[last1] +B[last2]
According to largest of them decrease last1 and last2.
this way you'll get Kth largest sum in k steps.

Comment if I am mistaken somewhere.

assuming arrays are sorted ascending order, will this work? ur comments are really appreciated. thx

public static int kthLargestSum(int [] a1, int [] a2, int k) {
		int maxSum = 0; 
		int a =  a1.length-1;
		int b = a2.length -1;
		for(int i = 0; i < k; i++) {
			maxSum  = 0;
			if(a1[a] < a2[b]) {
				maxSum+=a2[b];
				maxSum+=a1[a];
				a--;
			} else if(a1[a] > a2[b]) {
				maxSum+=a1[a];
				maxSum+=a2[b];
				b--;
			} else {
				maxSum+=a1[a];
				maxSum+=a2[b];
				b--;
			}
		}
		return maxSum;
	}