how to do it in space comp- O(1) . I mean without using additional arrays.
Could it be done ?
On Thu, Jun 14, 2012 at 3:46 PM, utsav sharma <utsav.sharm...@gmail.com>wrote:
> @all :- by segregating 0 and 1 or by taking quicksort approach
> we have to swap no.s resulting which array becomes unordered.
>
> my approach is start from right and if a negative no. occurs insert it
> into another array temp[]
> this will shift all positive no.s to right and in 2nd pass start from left
> of original array and insert all the elements of temp.
> time comp-O(n), space comp-O(n)
> correct me if i am wrong
>
> On Thu, Jun 14, 2012 at 1:53 PM, saurabh singh <saurab...@gmail.com>wrote:
>
>> Order may not be maintained necessarily by this solution
>>
>> Saurabh Singh
>> B.Tech (Computer Science)
>> MNNIT
>> blog:geekinessthecoolway.blogspot.com
>>
>>
>>
>> On Thu, Jun 14, 2012 at 1:47 PM, Manikanta Babu <
>> manikantabab...@gmail.com> wrote:
>>
>>> Check this out, it works in O(n);
>>>
>>> int i = 0;
>>> int j = n-1;
>>>
>>> while((i<n && j>= 0)&&(i<j))
>>> {
>>> if(a[i]>0 && a[j]<0)
>>> {
>>> swap(a[i],a[j]);
>>> i++; j--;
>>> }
>>> else
>>> {
>>> if(a[i]<0)
>>> i++;
>>> if(a[j]>0)
>>> j--;
>>> }
>>>
>>> }
>>>
>>> Thanks,
>>> Mani
>>>
>>> On Thu, Jun 14, 2012 at 1:05 PM, Mad Coder <imamadco...@gmail.com>wrote:
>>>
>>>>
>>>> As nothing is written about space complexity, I am assuming that we can
>>>> take extra space.
>>>>
>>>> Take a temporary array of length n.
>>>>
>>>> 1. Maintain a counter for the length of temporary array filled till now.
>>>>
>>>> 2. Traverse the given array. If value contained is negative insert it
>>>> in new array and update counter. After complete traversal all negative
>>>> values will be in the temporary array.
>>>>
>>>> 3. Traverse again the given array. Repeat step 2 but this time for
>>>> positive numbers.
>>>>
>>>> Finally temporary array contains the required answer. If required copy
>>>> it into original array.
>>>>
>>>> As this approach takes max. 3 traversals so its complexity is O(n).
>>>>
>>>> --
>>>> 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
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> Thanks & Regards,
>>> Mani
>>> http://www.sanidapa.com - The music Search engine
>>>
>>> --
>>> 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
>>> algogeeks+unsubscr...@googlegroups.com.
>>> 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Utsav Sharma,
> NIT Allahabad
>
> --
> 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
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
