Hey guys .. saw this discussion and wanted to add something .. I wrote the
below program in college .. and I kindof have forgotten wat was the logic
(see the problem with badly written code :P ), It works on a pattern which I
found in this problem, I checked it and feel it works in order O(n) as each
element is accessed only twice, if you guys find any problem do post it.
#include <stdio.h>
int main() {
int n, i, j , k, t1, l;
scanf("%d",&n);
int arr[n<<1 + 1];
for (i=1,j=n<<1,k=-1,l=0;i <= j ; i++ ) {
if ( i <= n )
arr[i] = k+=2; // 1 3 5 7
else
arr[i] = l+=2;
}
arr[0]=0;
printf("\n\nBefore Shuffling ..\n");
for (i = 0;i <= n<<1; i++) printf("%d ", arr[i]);
printf("\n\nShuffling Now ..\n");
// Shuffleing starts
i = 1;
int chk[j+1]; // To check if each element was visited only once
for (i=0;i<=j;i++) chk[i]=0;
i = 1;
while (i <= j) {
while (i<=j && arr[i] == i) {
chk[i]++;
i++;
}
if (i >j)
break;
t1 = arr[i]; // swap with temp
k = i; // note the curr. loc in array
l = i;
printf("%d : Value of i entering loop\n",i);
while (1) {
k = k & 1 ? (k + 1) / 2 : n + k / 2;
chk[k]++;
if (k == i) break;
arr[l] = arr[k];
l = k;
}
arr[l] = t1;
}
for (i = 0;i <= j;i++) printf("%d ",arr[i]);
printf("\n Checking which element was processed how many times.\n");
for (i = 0; i <= j; i++)
printf("%d %d\n",i,chk[i]);
return 0;
}
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.
On Sun, Jan 9, 2011 at 7:11 PM, Decipher <[email protected]> wrote:
> No its a single array . You have to convert first array into second in
> O(n) time and O(1) space .
>
> --
> 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%[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.
