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.


  1. Anonymous
    November 15, 2005 at 11:59 am

    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

  2. November 16, 2005 at 9:57 am

    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!


  3. November 16, 2005 at 10:43 am

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

    An:sorted array of n integers
    Bm:sorted array of m integers
    N:a number

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

    for i:2 to N
    if( A[j]+B[k-1] > A[j-1]+B[k] )
    return C;


    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]


    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.

  4. November 16, 2005 at 10:54 am

    It is wrong!

  5. November 16, 2005 at 11:04 am

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


  6. H
    April 18, 2006 at 5:59 pm

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

  7. Raja
    July 14, 2006 at 5:13 am

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

    int *func(int *, int *, int *, int , int , int);
    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];
    r[c] = a[0]+b[j+1];
    r[c] = a[k+1]+b[0];


  8. gaurav
    December 18, 2006 at 2:04 am

    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..

  9. Rahul
    February 13, 2007 at 4:34 am

    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;
    i = i-1;


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

  10. October 29, 2008 at 4:37 am

    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 :).

  1. September 2, 2006 at 4:52 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: