@gaurav. They way I see it it's O(nlogn)?
you have n/4 for each level of the recursion tree and logn height. In
total its O(nlogn)
On Feb 28, 9:27 pm, Vinay Pandey <babbupan...@gmail.com> wrote:
> Hi,
>
> Here is my solution, let me know:
>
> /* a helper function */
> void swap(int* arr, int index1, int index2) {
> /* this is only to swap to integers */
> arr[index1] = arr[index1]^arr[index2];
> arr[index2] = arr[index1]^arr[index2];
> arr[index1] = arr[index1]^arr[index2];
>
> }
>
> /* Actual switching */
> void switch(int* arr, int length) {
> if(length%2!=0 && length<2) {
> cout<<"Cannot switch in this case";
> return;}
>
> int index = length-1, first=0, second=0;
> bool flag = 0;
> while(index>=2) {
> if(flag == 0) {
> swap(arr, (index+1)/2, index);}
>
> if(flag == 1) {
> swap(arr, index/2 + 1, index);
> swap(arr, (index+1)/2, index);}
>
> index-=2;
> flag=(flag==0)?1:0;
>
>
>
>
>
>
>
> }
> }
> On Mon, Feb 28, 2011 at 4:32 PM, Dave <dave_and_da...@juno.com> wrote:
> > @Arpit: The problem is that for certain values of n, you get more than
> > one cycle, and the cycles are disjoint. You have to find all of the
> > disjoint cycles and move the elements in each one.
>
> > Dave
>
> > On Feb 28, 12:25 pm, Arpit Sood <soodfi...@gmail.com> 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 <shashank7andr...@gmail.com>
> > 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 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.-Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > 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.
