I tried implementing the problem.
Working code is:
#include <stdio.h>
void print_arr(int* arr, int len)
{
int i;
printf("\n Array is \n");
for (i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int get_right_index(int i, int len)
{
if (i < len/2) {
return 2*i;
}
return 2*(i-len/2)+1;
}
int get_right_candidate(int i, int len)
{
if (i%2) {
return (i-1)/2 + len/2;
}
return i/2;
}
void make_pattern(int* arr, int len)
{
if (len%2) {
return;
}
if (len == 2)
{
return;
}
int total_no_assign = 0;
int index = 1;
while (total_no_assign < (len -2)) {
int cur = index;
int val = arr[cur];
int target_index = get_right_index(cur, len);
if (val < 0) {
printf("\n Already shuffled");
index++;
continue;
}
while(cur != target_index) {
int ci = get_right_candidate(cur, len);
arr[cur] = 0 - arr[ci];
printf("\n Index shuffled cur = %d, ci = %d\n", cur, ci);
cur = ci;
total_no_assign++;
print_arr(arr, len);
}
arr[cur] = 0 - val;
total_no_assign++;
print_arr(arr, len);
}
int i;
for (i = 0; i < len; i++) {
if (arr[i] < 0) {
arr[i] = 0 - arr[i];
}
}
}
int main()
{
int count;
int* arr;
printf("\nEnter no of elements (array elemnts should be striclty greater
than 0) ");
scanf("%d", &count);
if (count%2) {
return -1;
}
arr = (int*) malloc(sizeof(int)*count);
if (!arr) {
return;
}
int i;
for ( i = 1; i <= count; i++)
{
printf("\nEnter element %d ", i);
scanf("%d", &arr[i-1]);
}
print_arr(arr, count);
make_pattern(arr, count);
print_arr(arr, count);
return 0;
}
Please correct me if the code is wrong.
I tested with few inputs.
On Mon, Feb 7, 2011 at 11:43 PM, yq Zhang <zhangyunq...@gmail.com> wrote:
> @above, "if initial position=final position or the final position was
> empty,then choose the next element(element next to the initial position) as
> current element"
>
> How do you guarantee when you move to the next element, the next element is
> not already processed? Otherwise, you will double process on element.
>
>
>
> On Mon, Feb 7, 2011 at 9:36 AM, jalaj jaiswal
> <jalaj.jaiswa...@gmail.com>wrote:
>
>> algo in more detail :-o
>>
>> if the array is numbered from 0..(2n-1)
>>
>> i= initial position of int/char
>> f= final position of int/char
>>
>> if (i < (2n-1)/2) #for integer
>> f = i+i
>> else #for char
>> f = i - ((2n-1)-i)
>>
>> so iterate through the array in the following way
>>
>> choose first element
>> determine it final position
>> put the element in the final position
>> the next element to be processed is the original element in the final
>> position
>> if initial position=final position or the final position was empty,then
>> choose the next element(element next to the initial position) as current
>> element
>>
>> stop when last element has been processed.
>>
>> eg
>> 1234abcd
>> current = 1
>> i = 0
>> f = 0+0 = 0
>>
>> i=f
>> so current= next element= 2
>> i=1
>> f=1+1=2
>> put 2 in 2nd position
>> 1-24abcd
>>
>> current element = original element in 2nd position = 3
>> for 3
>> i = 2
>> f=2+2=4
>>
>> so put 3 in 4th position
>> 1-243bcd
>> current =a
>> i=4
>> f=(i - ((2n-1)-i) = (4-(7-4)) = 1
>> 1a243bcd
>>
>> now final position was empty
>> so next element = intital position +1
>> = intitial position of a +1 =
>> 4 +1 = 5
>>
>> current = b
>> processing in a similar way
>>
>> 1a2b3-cd
>> current = 4
>> 1a2b3-4d
>> current = c
>> 1a2b3c4d
>> current = d
>> 1a2b3c4d
>>
>> processed last element so stop
>>
>>
>>
>> can't explain more better :-o
>>
>>
>> On Mon, Feb 7, 2011 at 10:59 PM, Manmeet Singh <mans.aus...@gmail.com>wrote:
>>
>>> thr is some error in algo
>>>
>>>
>>> On Mon, Feb 7, 2011 at 10:48 PM, abc abc <may.i.answ...@gmail.com>wrote:
>>>
>>>> I would like to have pseudo for this .
>>>>
>>>> On Mon, Feb 7, 2011 at 11:12 AM, jalaj jaiswal <
>>>> jalaj.jaiswa...@gmail.com> wrote:
>>>>
>>>>> A very common interview question
>>>>>
>>>>> let the array be from 0 to 2n-1
>>>>>
>>>>> now,
>>>>>
>>>>> every element of array has its initial position and final position..
>>>>> start from beginning
>>>>> if the elemnt you r processing is the first half of array then f=i+i;
>>>>> else f=2*i-(2n-1);
>>>>> replace the elemnt at final position with the initial element .. now
>>>>> next elemnt to process will be oroginal elemnt at final position
>>>>> if the final position is empty or the same position then process next
>>>>> element to the initial position.
>>>>> do until you process the last element.
>>>>>
>>>>> inplace with O(n).
>>>>>
>>>>>
>>>>> On Mon, Feb 7, 2011 at 8:32 AM, may.I.answer
>>>>> <may.i.answ...@gmail.com>wrote:
>>>>>
>>>>>> If [a1,a2,a3...,an,b1,b2...bn] is given input change this to
>>>>>> [a1,b1,a2,b2.....an,bn]
>>>>>>
>>>>>> --
>>>>>> 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.
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> With Regards,
>>>>> *Jalaj Jaiswal* (+919019947895)
>>>>> Final Year Undergraduate,
>>>>> IIIT ALLAHABAD
>>>>>
>>>>> --
>>>>> 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.
>>>
>>
>>
>>
>> --
>> With Regards,
>> *Jalaj Jaiswal* (+919019947895)
>> Software developer, Cisco Systems
>>
>> Final Year Undergraduate,
>> IIIT ALLAHABAD
>>
>> --
>> 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.
