Geany
BAN USERhere'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.
I guess its easy and self explanatory.....
I have checked it for some cases....
Do comment if its wrong....
#include<stdio.h>
#include<stdlib.h>
static char arr[] = {"NNNLLLL"};
static int index;
struct node{
char value;
struct node *left;
struct node *right;
};
struct node* newnode(char val)
{
struct node *temp = (struct node*) malloc(sizeof(struct node*));
temp->value = val;
temp->left = NULL;
temp->right = NULL;
return temp;
}
struct node* maketree(){
struct node *temp = newnode(arr[index]);
if(temp->value == 'L')
{
index++;
return temp;
}
else if(temp->value == 'N')
{
index++;
temp->left = maketree();
temp->right = maketree();
}
return temp;
}
int main(){
struct node * root;
root = maketree();
getchar();
return 0;
}
It also doesn't cover the case of 3241, when entered 4..
- Geany March 29, 2012