Sorry, small mistake in designated index calculation.
It should be k*p2 % (n-1) instead of (k*p2 -1) % (n - 1).
Thanks,
- Ravindra
On Thu, Nov 3, 2011 at 11:37 PM, ravindra patel <ravindra.it...@gmail.com>wrote:
> 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 <sinv...@gmail.com> 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 <srn...@gmail.com> 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 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.
>>
>
>
--
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.
