I forgot to mention
Time complexity: O(n), Space complexity: O(1)
Assuming you accept my solution :-)
On Mon, Feb 28, 2011 at 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.
