it can be done in O(m) . Use something like binary search .
code is here .......
#include<stdio.h>
void splitMN(int a[],int m , int b[], int n){
int al = 0 , bl = 0 ;
int ah = m-1 , bh = n-1 ;
int ai = (ah+al+1)/2;
int bi = (bh+bl+1)/2;
while(ai+bi!=m){
printf("Enter ai = %d, bi = %d\n ",ai,bi);
if(ai+bi < m){
if(a[ai] < b[bi]){
al = ai ;
if(al == ai) break;
ai = (ah+al+1)/2;
}else{
bl = bi ;
if(bh == bi) break;
bi = (bh+bl+1)/2;
}
}else{
if(a[ai] > b[bi]){
ah = ai ;
if(ah == ai) break;
ai = (ah+al+1)/2;
}else{
bh = bi ;
if(bh == bi) break;
bi = (bh+bl+1)/2;
}
}
}
bi = 0 ;
ai ;
while(ai < m){
a[ai] = a[ai]^b[bi]^(b[bi] = a[ai]);
ai++ ; bi++ ;
}
}
int main(){
int m , n ;
printf("Enter m , n : ");
scanf("%d%d",&m,&n);
int a[m] , b[n] ;
int i ;
for(i = 0 ; i< m ; i++)
scanf("%d",&a[i]);
for(i = 0 ; i< n ; i++)
scanf("%d",&b[i]);
printf("Enter m , n : ");
splitMN(a,m,b,n);
for(i = 0 ; i< m ; i++)
printf("%d\t",a[i]);
printf("\n");
for(i = 0 ; i< n ; i++)
printf("%d\t",b[i]);
printf("\n");
}
On Sat, Jun 4, 2011 at 4:03 AM, Aakash Johari <[email protected]> wrote:
> Please try this solution. And tell if it fails at any case. If it works
> fine, I will tell the logic.
>
>
>> #include <stdio.h>
>> #include <stdlib.h>
>>
>> void merge(int *a, int m, int *b, int n)
>> {
>> int i, j, k;
>> int t;
>>
>> i = j = 0;
>> k = -1;
>>
>> while ( i < m && a[i] < b[j] ) {
>> i++;
>> }
>>
>> while ( i < m && j < n ) {
>> if ( k == -1 && b[j] < a[i] ) {
>> t = a[i]; a[i] = b[j]; b[j] = t;
>> k = j;
>> j++;
>> i++;
>> } else if ( b[j] < b[k] ) {
>> t = a[i]; a[i] = b[j]; b[j] = t;
>> j++;
>> i++;
>> } else {
>> t = a[i]; a[i] = b[k]; b[k] = t;
>> i++;
>> }
>> }
>> }
>>
>> int main()
>> {
>> int m, n;
>> int *a, *b;
>> int i;
>>
>> scanf ("%d%d", &m, &n);
>>
>> a = (int*) malloc(sizeof(int) * m);
>> b = (int*) malloc(sizeof(int) * n);
>>
>> for ( i = 0; i < m; i++ )
>> scanf ("%d", a + i);
>>
>> for ( i = 0; i < n; i++ )
>> scanf ("%d", b + i);
>>
>> merge (a, m, b, n);
>>
>> printf ("After Merge Operation : \n");
>>
>> printf ("1st Array : ");
>>
>> for ( i = 0; i < m; i++ ) {
>> printf ("%d ", a[i]);
>> }
>>
>> printf ("\n2nd Array : " );
>>
>> for ( i = 0; i < n; i++ ) {
>> printf ("%d ", b[i]);
>> }
>>
>> return 0;
>> }
>>
>>
>> On Fri, Jun 3, 2011 at 8:07 AM, bittu <[email protected]> wrote:
>
>> @sravanreddy...logical bugs if A is size of n & B is size m from your
>> example assuming n<m so if you want smallest m elements in A then u
>> only capacity of n elements & didn't allocate memory so these elements
>> initialized by INT_MIN for m-n nodes so that array A can hold m
>> smallest elements then what r u swapping u dude..isn't garbage
>> value ?? you will get at 1st step only just run it ?? in you algo
>> A_End=m-1(which 4th position in Array that DNE)..?? & also you have to
>> free memory for m-n in array B as it contains n largest elements .
>>
>> take
>> A= 1,2,3 n=3
>> B= 0,1,4,5,9 m=5
>>
>> after allocating memory to Array A for m-n elements A will looks
>> likes 1 2 3 INT_Max INT_Max
>> now what you wants A should contains m smallest elements & B have n
>> largest elements
>> so O/P should be A=1,2,3,1,0 & B=INT_Max,INT_Max,4,5,9 now free
>> memory used by 1st elements in array B so that A will represent M
>> smallest elements & B will have n Largest elements
>>
>> so that above will work.
>>
>> Hope I am Correct let me know if any issue with explanation
>>
>> Thanks
>> Shashank>>"The Best Way To Escape From The problem is To Solve It"
>> CSE,BIT Mesra
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> -Aakash Johari
> (IIIT Allahabad)
>
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
*With Regards :*
Ravinder Kumar
B.Tech 3rd Year
Computer Science and Engineering
MNNIT Allahabad
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
