Home
> Computer Programming, Computer Science, Problem Solving/Puzzles > Try this problem and if you find a solution do ping me!

## Try this problem and if you find a solution do ping me!

Two sets A = {a0,a1,a2,…,an} and B = {b0,b1,b2,…,bn} having integer in increasing order (Sorted arrays of size n). We have to select n largest numbers from the set {ai+bj} ( This set is the sum of two numbers one taken from set A and one taken from set B. The task is to get n largest numbers in O(n). I have tried it many times and found very close solutions that fails on 5%cases. Though at times i think of improving the solution but i am really tired of this. So if any one finds the correct solution with proof do mail me.

Regards,

Advertisements

Categories: Computer Programming, Computer Science, Problem Solving/Puzzles

Nice Blog!!! I thought I’d tell you about a site that will let give you places where

you can make extra cash! I made over $800 last month. Not bad for not doing much. Just put in your

zip code and up will pop up a list of places that are available. I live in a small area and found quite

a few. MAKE MONEY NOW

Please furthar elaborate the problem, I don’t understand what is input of this problem, and what is C[Ai+Bj], a worst case example will do, if possible!

BYE,

muDASir.

Hi,

My solution is sort of modified Reverse Merge sort. See it.

Input:

An:sorted array of n integers

Bm:sorted array of m integers

N:a number

Output:

CN:sorted array of top N integers in supposed array X[Ai+Bj]

Algorithm:

Solve(A,B,N)

{

C[1]=A[n]+B[m]

j=n

k=m

for i:2 to N

{

if( A[j]+B[k-1] > A[j-1]+B[k] )

{

k–;

}

else

j–;

C[i]=A[j]+B[k];

}

return C;

}

Complexity:

A single loop of N.

so theta of N

Prooof by induction:

1. Initial condition is true as largest number is always A[n]+B[m]

2. if A[i]+B[j] if xth largest number then

x+1the largest is

A[i]+B[j-1] ;A[i] is larger than A[i-1]…A[1] and B[j-1] is larger than B[j-2]…B[1]

or

A[i-1]+B[j] ;A[i-1] is larger than A[i-2]…A[1] and B[j] is larger than B[j-1]…B[1]

Also A[i-1]+B[j-1] can’t be the solution as either of the above two is always larger than or equal to it.

Hence larger of two is x+1th largest number. So this solution will reveal N largest numbers in N.

It is wrong!

Yes Muddasir this is surely wrong, try again and stop trivialities.

Haroon

That solution is incorrect. You actually need to start from the last position again.

Hi,

I used simple recursion . jus check out and mail me if any errors .

#include

#include

int *func(int *, int *, int *, int , int , int);

main()

{

int a[3]={5,4,3},b[3]={3,1,0},r[3]={0},*result;

result=(int *)malloc(sizeof(int)*3);

int j=0,k=0,c=0;

r[0] = a[0] + b[0];

result=func(a,b,r,c,j,k);

for(j=0;j(a[k+1]+b[0]))

{

r[c] = a[0]+b[j+1];

j++;

}

else

{

r[c] = a[k+1]+b[0];

k++;

}

func(a,b,r,c,j,k);

}

Cya,

Raja.

i guess if u have 2 sorted arrays and u start from the last elements of them both..

compare the last element from the 2 arrays.. chk out the bigger element and put it in at the end of a third empty array, then move the pointer to left by 1 from the array from which u moved the larger element, do this till the lists are exhausted..guess this shd work..

I haven’t tested the recursive solution posted. So this may be just an extra post (but I figured I might as well add my 2 cents)

Pseudo code:

– Let A and B be the arrays and i and j be their resp. indices, let SOL be the solution array in descending order (higher number at SOL[0])

i = n; j = n;

for x = 0 to n-1

{

SOL[x] = A[i] + B[j];

if ((A[i] – A[i-1]) > (B[j] – B[j-1]))

j = j-1;

else

i = i-1;

}

*********

This O(n) (Trivially!). Let me know if you need a proof of correctness for the algorithm.

Hello Rahul,

Your solution won’t work correctly. Consider

Array1: 3, 4, 7, 8

Array2: 9, 15, 18, 20

Now according to your code.

Iteration1: i = 4, j = 4 Max = 20 + 8 // Correct

Iteration2: i = 4, j = 3 Max = 20 + 7 // Correct

Iteration2: i = 3, j = 3 Max = 18 + 7 // InCorrect max is be 18+8.

I think we should keep trying :).