Here is one recursive solution I propose :
consider example a1,a2,a3,a4,b1,b2,b3,b4
1. if n is even
swap second Half of first array with first half of second array
so it would be a1,a2,b1,b2,a3,a4,b3,b4
and it can be solved recursively
so rearrange({a1,a2,a3,a4,b1,b2,b3,b4}) = rearrange({a1,a2,b1,b2}),
rearrange({a3,a4,b3,b4});
2. if n is odd (a1,a2,a3,a4,a5,b1,b2,b3,b4,b5)
swap second Half+1 of first array with first half+1 of second array
so it would be a1,a2,b1,b2,*b3,a3*,a4,a5,b4,b5
swap bolded elements( nth and n+1 th) a1,a2,b1,b2,a3,b3,a4,a5,b4,b5
and it can be solved recursively by dividing in two sub parts
rearrange({a1,a2,a3,a4,a5,b1,b2,b3,b4,b5}) = swap(b3,a3),
rearrange({a1,a2,b1,b2}), rearrange({a4,a5,b4,b5});
limiting case would be
if n==2 //since the pair is in required order
return;
Time complexity analysis ( n is size of total array a+b):
T(n) = 2*T(n/2) + n/4 ( n/4 is swapping time of second Half of first array
with first half of second array)
T(n) = 2^k T(1) + n/4( 1+1/2+1/4+.......+1/(2^k))
= 2^k+n/4( 1-1/(2^k))*2 k = log(n)
=n+ (n-1)/2
=O(n)
What say?
On Mon, Feb 28, 2011 at 11:55 PM, Arpit Sood <[email protected]> wrote:
> well space complexity should be mentioned in the question then, anyway,
> start with the second element put it at its correct location(say x), then
> take x put it at its correct location, this was when you do this n-1 time,
> you will get the correct answer because it forms a cycle.
>
>
> On Mon, Feb 28, 2011 at 11:33 PM, bittu <[email protected]>wrote:
>
>> @arpit otherwise it wont b amzon quest..
>> space dude..space is constants
>>
>>
>> Thanks
>> Shashank
>>
>> --
>> 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.
>>
>>
>
> --
> 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.
>
--
Thanks & Regards,
Gaurav Gupta
7676-999-350
"Quality is never an accident. It is always result of intelligent effort" -
John Ruskin
--
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.
