This is a special case of shuffling problem. In shuffling problem we have
to merge k (here k = 3) parts of array such that each kth element is from
the same sub-array and in same order. For eg -
a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should become => a1 b1 c1 a2 b2 c2 a3
b3 c3 a4 b4 c4.
Usually shuffling problem can be solved only in O(n*logn) time without
additional space, but here you have an added advantage. You know what the
sequence should look like exactly. So here goes the O(n) solution with
constant space.
1- Take 2 pointers p1 and p2 initialize both of them to index 1 (second
element)
2- now for each element at p2 find the right index where it should go and
put it thr. The right index is -
(k*p2 -1) % (n-1); // k=3 here
3- Keep doing it until p2 becomes same as p1 again.
4- Now advance p1 till the elements are in order 0 1 2 0 ....
5- if p1 is less than n-1 than set p2 = p1. Repeat thru step 2-5 again.
Here is a primitive C code to do the same.
int p1 = p2 = 1;
int preVal, next, temp;
while (p1 < n)
{
preVal = a[p1];
p2 = p1;
do{
next = (k*p2 -1) % (n-1); // k=3 here
temp = a[next];
a[next] = preVal;
preVal = temp;
p2 = next;
} while (p2 != p1)
while(p1 < n)
{
if( ((a[p1] - a[p1-1]) == 1) || (a[p1] - a[p1-1]) == -2)) //
elements are in sequence 0 1 2 0
p1++;
else
break;
}
}
Feedback welcome :-).
- Ravindra
On Wed, Nov 2, 2011 at 6:43 PM, shady <[email protected]> wrote:
> any solutions for this ?
> dutch national flag problem could be done in O(n) time and O(1) space by
> considering two pointers, but how to do this (reverse dutch national flag
> problem) ?
>
>
> On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal <[email protected]> wrote:
>
>> Suppose we are given a string 000011112222.
>>
>> Make it 012012012012 in O(n) time and O(1) space.
>> Sanju
>> :)
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
