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 <[email protected]> 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 <[email protected]>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 [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
