In the final position, element at arr[0] remains at arr[0] arr[1] comes at arr[3] arr[2] comes at arr[6] arr[n] comes at arr[3n-3] position So element at k goes at 3k, if 1 <= k < n
arr[n] comes at arr[1] arr[n+1] comes at arr[4] arr[n+2] comes ar arr[7] arr[2n-1] comes ar arr[3n-2] So element at k goes at (k-n)*3+1, if n <= k < 2n arr[2n] comes at arr[2] arr[2n+1] comes at arr[5] arr[2n+2] comes at arr[8] arr[3n-1] remains at arr[3n-1] So element at k goes at (k-2n)*3+2, if 2n <= k < 3n-1 So, we can have a function req_pos which will return the required position for a number if its current position is given. int req_pos (int k, int n) { if (k < n) { return 3*k; } if (k < 2n) { return (k-n)*3+1; } return (k-2n)*3+2; } int k=1; for (int i=0; i<3n-1;i++) { int new_k = req_pos (k); swap (arr, k , new_k); k = new_k; } The above loop runs 3n times, which is sufficient to cover all the numbers. Only problem is that if k becomes equal to any previous value already covered, then it will fall into a loop and swap already swapped integers. If someone can prove that this will not happen, then we have an O(n) in-place solution. For n=10, k will have values like: 1, 3, 9, 27, 23, 11, 4, 12, 7, 21, 5, 15, Yoo-hoo... seems like it works! Please comment. On Jul 22, 7:02 pm, Ashish Goel <ashg...@gmail.com> wrote: > 123456789 > then interchange middle one of 123 and 456 > 12 43 56 789 > now exchange in pairs except first and last i.e. 24 ->42, 35->53 > 1 42 53 6 789 > now treat 14 as single number, 25 as single number ans 36 as single number > and again apply this logic > 14257 36 89 > 14 725 836 9 > > need time to program this, a bit busy... > > done :) > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > On Thu, Jul 22, 2010 at 5:58 PM, UMESH KUMAR <kumar.umesh...@gmail.com>wrote: > > > > > Qn:-in the given array elements > > a1a2a3a4......anb1b2b3b4.......bnc1c2c3c4........cn > > without take a extra memory how to merge just like? > > > a1b1c1a2b2c2a3b3c3............................anbncn > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.