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

    BYE,
    muDASir.

  3. November 16, 2005 at 10:43 am

    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.

  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.

    Haroon

  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

    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.

  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;
    else
    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: