An old question

Not that it has been long since I left college, but I remember once when I was preparing for my placements, I came across an interesting problem which is:
An array {A1,A2,A3,….,An,B1,B2,……,Bn} is given and we have to rearrange it as {A1,B1,A2,B2……} .Give an algo with minimum time and space complexity

I got it here, this is an awesum forum BTW, I really liked it and definitely plan on following it soon.

I remember spending a lot of time on it and discovering a pattern in the solution. Today, I saw this problem somewhere else and I remembered to have done some investigation over it. Luckily I found the code for it which I had written then, but unfortunately, I forgot the pattern 😛 and now I am too lazy to pick up the pen and paper and start all over again. I’l post the code here, I feel it’s O(1) space and O(n) time, but looking at the level of discussion at the forum I pointed to I feel something is wrong in the code. Can you find it for me ??

Also looking at this code of mine, for the first second, I couldn’t make out any sense of it and suddenly I realized the importance of comments and clean code. 🙂

#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;
}
Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: