OK. I hope following should do the needful.
Input:
a1,a2,a3,a4,.....aN,b1,b2,b3,b4,.....,bN
Output:
a1,b1,a2,b2,a3,b3,a4,b4,..........aN,bN.
If we notice, there is a pattern for all elements while shuffling.
For all elements from 1st half portion (a1 to aN)
a[i] is moved to a[2*i] where 0<= i <= N [say array name is a]
i.e.
a[0] is moved to a[0] (for i=0, i = 2*i =0)
a[1] is moved to a[2]
a[2] is moved to a[4]
a[3] is moved to a[6]
......
....
For 2nd half, same is true from opposite (OR if we see array
inverted,b1 to bN behaves same as a's)
In other words, keeping array as is, 2nd half of the array (b1 to bN)
goes like this
a[i] is moved to a[n-2*(n-i)] where N < i < 2N
i.e. (Assuming 2nd half array starting with index i=7, so total array
size 12)
a[7] moved to a[1]
a[8] moved to a[3]
a[9] moved to a[5]
overall as example:
Input
a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10],
a[11]
Output:
a[0], a[6], a[1], a[7], a[2], a[8], a[3], a[9], a[4], a[10], a[5],
a[11]
And I believe it's pretty straightforward to implement this. using
only few extra variables [not dependent on array size](Based on
implimentation).
So, O(n) time and O(1) space.
Alg: [assuming all elements are > 0)
Negate all elements (a[i] = -1 * a[i];)
current_index = 0;
current_element=A[0];
do
if current_index <= n/2 then
to_index = 2*current_index
else
to_index = (size -1) - 2*(size - 1 - current_index)
end if
current_element = A[to_index];
A[to_index] = -1 * A[current_index];
if current_element > 0 then
to_index = index of next negative element.
current_index = to_index;
while A[current_index] < 0
Algo can be modified to check in other cases like when elements can be
negative also, OR elements are characters, strings.
There can be different ways to track if all elements are processed or
not, depending on problem.
e.g. if negative elements are also in input then,
Add some very very negative no to all elements say -50000 and while
assigning it to to_index, adding 50000
If element are characters, string then attach some keyword (prefix or
suffix) to each element,
while assigning it to to_index, remove the attachment.
Please advise if you find any issue with this.
On Jan 10, 5:51 pm, juver++ <avpostni...@gmail.com> wrote:
> There is only one single array.
--
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.
