[algogeeks] Re: hi..plz solve this..

Thu, 06 Jul 2006 05:50:06 -0700

Hi dude,
       it has only one more element to be moved in the extra space. Other elements use the existing array as the space so space complexity is O(1) clearly.

 
On 7/6/06, Vishal <[EMAIL PROTECTED]> wrote:
What about O(1) space complextity? I think your solution has space complexity of O(n).
 

~Vishal


On 7/6/06, Arunachalam < [EMAIL PROTECTED] > wrote:
Hi,
     can you please elaborate on your question?
 
If I understand you correct then you are given an array of Length 2n with elements a1,a2...an,b1,b2.. bn.
 
Now you are asked to modify the array to a1,b1,a2,b2.....an,bn.
 
If this is the problem then the solution is straight forward. For each element not in place try to find its destination. Make a backup of the destination and then put this element there and mark the current location as empty. Now Keep on doing this until the destination reaches an empty place. When destination reaches empty place restart the process.
 
This is of O(n) Since at the first time itself the element will be moved to its place. And for the element in its place we will not do any processing. So this is clearly of order n.
 
If this is not your question then please do state your question clearly.
 
regards
Arunachalam.

 
On 7/6/06, subrahmanyam kambala <[EMAIL PROTECTED] > wrote:
array contains 2n numbers like a1a2a3a4a5...anb1b2b3...bn

i want the array in such a way that a1b1a2b2a3b3.....anbn

in O(n) time complexity and O(1) space complexity..
i got with O(nlogn) complexity...

is it possible ?




 



http"//ww.livejournal.com/users/arunachalam
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to