CareerCup

<pre lang="" line="1" title="CodeMonkey23279" class="run-this">class ArrayOperation {

public static void main(String[] args) {
char[] a = "123456789abcdefghi".toCharArray();
mixArray(a, 0, a.length -1);
for(char item : a) {
System.out.print(item + " ");
}
}
/**
* Question :
* Suppose we have an array like
* 1,2,3,4,5,a,b,c,d,e where we have always even number of elements.First half of the elements
* are integers and second half are alphabets we have to change it to like
* 1,a,2,b,3,c,4,d,5,e in place i.e no use of any extra space, variables are allowed ..
*
* @param a
*/
public static void mixArray(char[] a, int start, int end){
assert((end - start + 1) % 2 == 0);
if (start +1 >= end)
return;

// swap the every element after start with (end - start)/2 th item after it
// 1 2 3 4 5 a b c d e becomes 1 a b c d 2 3 4 5 e
int distance = (end - start) / 2;
for(int i = start + 1; i + distance < end; i++) {
swap(a, i, i + distance);
}

// swap element back to origin place except head and tail
// 1 a b c d 2 3 4 5 e becomes 1 a 2 3 4 b c d 5 e
distance = (end - start - 2) / 2;
for(int i = start + 2; i + distance < end - 1; i++) {
swap(a, i, i + distance);
}

// recursive call to mix the rest
mixArray(a, start + 2, end - 2);
}

private static void swap(char[] a, int i, int j) {
char temp = a[i];
a[i] = a[j];
a[j] = temp;
return;
}
}
</pre><pre title="CodeMonkey23279" input="yes">
</pre>

Here is one with linear time and constant space:

void shuffle(int A[], int n)
{
	int start = 1;
	int count = 0;
	for(int i = 0; count < n - 3; i++)
	{
		int dest;
		if(start < n / 2)
			dest = (2 * start) % n;
		else
			dest = (2 * start + 1) % n;
		while (start != dest)
		{
			swap(A[start], A[dest]);
			count++;
			if(dest < n / 2)
				dest = (dest * 2) % n;
			else
				dest = (dest * 2 + 1) % n;
			
		}
		count++;
		start += 2;
	}
}

Start with element in the second location move it to its destination. Pick the element that was present previously at destination and move it to its required position. Repeat until you land at your initial start location, this forms a cycle so you can pause. If all elements have been moved to their destination stop if not start with location initial start + 2 and repeat until done.

int newSortArr(int *arr, int nLength)
{
if (NULL == arr)
return 0;

int i = 1;
int j = nLength-2;
int mid = nLength>>1;
while (i < j)
{
for (int m = i;m < mid;m++)
swap(arr+m,arr+mid+m-i);
i++;
j--;
}
return 1;
}

Check this soln

void sortSe(char a[],int low,int high)
{
int mid = (low+high)>>1;
int j=mid+1,i=mid;
if(high-low<=1)
 return;
 swap(a[mid],a[mid+1]);
 while(i>low+1)
 {
 swap(a[i],a[i-1]);
 swap(a[j],a[j+1]);
 j++;
 i--;
 }
sortSe(a,low+2,high-2);
     
}

How the above code works - >
1 2 3 4 a 5 b c d
1 2 3 a 4 5 b c d
1 2 3 a 4 b 5 c d
1 2 a 3 4 b 5 c d
1 2 a 3 4 b c 5 d
1 a 2 3 4 b c 5 d
1 a 2 3 4 b c d 5
1 a 2 3 b 4 c d 5
1 a 2 b 3 4 c d 5
1 a 2 b 3 c 4 d 5

I guess this should work. But this is O(n*n) soln. but I guess there has to exist a O(nlogn) soln.

for(i=len/2;i<len;i++){
j=i;
while(j>2*(i-(len/2))){
int swap = arr[j];
arr[j]=arr[j-1];
arr[j-1] = swap;
j--;
}
}

What if we use two pointers slow and fast and use alternate split method to reach the center of the array. And then we can exchange the digits with alphabets keeping in mind about even places.

Though I have not seen Above Cited Ideas and Solution..might be Some1 already gave the same

1 2 3 4 5 a b c d e <----Leave 1 and e Coz Resultant position is unchanged
------------------- First Pass
1 2 3 4 a 5 b c d e
1 2 3 a 4 5 b c d e
1 2 a 3 4 5 b c d e
1 a 2 3 4 5 b c d e
------------------- Second Pass
1 a 2 3 4 b 5 c d e
1 a 2 3 b 4 5 c d e
1 a 2 b 3 4 5 c d e
------------------- Third Pass
1 a 2 b 3 4 c 5 d e
1 a 2 b 3 c 4 5 d e
------------------- Fourth Pass
1 a 2 b 3 c 4 d 5 e <----Here We get the Resultant Array

Idea Is very much Simple.I will be giving Pseudo Code soon.

I am submitting very rough but working Code and I believe this is one of the simplest Solution..Also refer Flow from my previous comment i Posted here (Rex on October 26, 2011) in the same thread.

//Now Scan 10 for the elements,Though you can make this code generic for any length.

#include<stdio.h>
#include<string.h>

int main()
{

char a[15]={'1','2','3','4','5','a','b','c','d','e'};
int i=1, j,k,p,pass=0,l;
int t;
printf("How many elements are in an Array:");
scanf("%d", &k);
j=(k-1)/2;
for(i=0;i<k;i++)
printf(" %c " ,a[i]);
puts("\n");

i=1;
while(1)
{ if(pass==k)
break;

//Effective Code

for(t=j;t>=i;t--)
{

a[t]^=a[t+1]^=a[t]^=a[t+1];

for(l=0;l<k;l++)
printf(" %c " ,a[l]);

puts("");
pass=pass+1;
}

puts("");
i=i+2;
j=j+1;
}

puts("");
for(i=0;i<k;i++)
printf(" %c " ,a[i]);

puts("");
return 0;
}

Optimize the code as per your requirement.


-Rajan

Here is one with linear time & constant space:

void shuffle(int A[], int n)
{
	int start = 1;
	int count = 0;
	for(int i = 0; count < n - 3; i++)
	{
		int dest;
		if(start < n / 2)
			dest = (2 * start) % n;
		else
			dest = (2 * start + 1) % n;
		while (start != dest)
		{
			swap(A[start], A[dest]);
			count++;
			if(dest < n / 2)
				dest = (dest * 2) % n;
			else
				dest = (dest * 2 + 1) % n;
			
		}
		count++;
		start += 2;
	}
}

Start with the second element move it to its destination. Pick the element that was previously located at destination and repeat move until you end at the location you started initially. If more elements need to be swapped repeat the previous steps from location start + 2.

static void changeSeq (){
		char[] arr = "12345abcde".toCharArray();
		int len = arr.length;
		int k=0;
		for (int i=len/2;i<len-1;i++){
			for (int j=i-1;j>=(2*k+1);j--){
				char temp = arr[j+1];
				arr[j+1]=arr[j];
				arr[j]=temp;
			}
			k++;
			System.out.println(arr);	
		}
	}

#include <string>
#include <iostream>

using namespace std;

void change(string& s,int a, int b)
{
if (a>=b)
return;
int x = (a+b)/2;
int y = x+1;
swap(s[x],s[y]);
for (x--;x>=a;x--,y++)
{
swap(s[x],s[x+1]);
swap(s[y],s[y+1]);
}
change(s,a+2,b-2);
}

int main()
{
string word;
cin >> word;
change(word,0,word.size()-1);
cout << word << endl;
return 0;
}

#include <string>
#include <iostream>

using namespace std;

void change(string& s,int a, int b)
{
  if (a>=b)
    return;
  int x = (a+b)/2;
  int y = x+1;
  swap(s[x],s[y]);
  for (x--;x>=a;x--,y++)
    {
      swap(s[x],s[x+1]);
      swap(s[y],s[y+1]);
    }
  change(s,a+2,b-2);
}

int main()
{
  string word;
  cin >> word;
  change(word,0,word.size()-1);
  cout << word << endl;
  return 0;
}

Tried in O(n) but no joy. Following is O(n^2)

AS(i, j)
	if(i < 0 && j > 2*n-1)
		return
	t = a[j]
	for each k from j-1 to i+1
		a[k+1] = a[k]
	a[i+1] = t	
	AS(i-1, j+1)

main()
	m = (n+1+2n)/2
	for each i from n+1 to m and j from 2n to m
		swap(i, j)
	AS(n-1, n)

I believe the following is a O(n) solution.

The approach is to move left to right and swap character values as required.

Some notes:
// i holds the current position.
// k holds the position of the first alphabetic character that has
// not been swapped.
// The initial value points to 'a'.
// int k = n/2;
// j holds the position of the first numeric character to be swapped.
// The initial value set to -1.

// Note that the last two entries will already be swapped so I am only iterating to n-2.

Comments appreciated.

void transformArray()
{
   const int n = 10;
   char a[n] = {'1', '2', '3', '4', '5', 'a', 'b', 'c', 'd', 'e'};

   int k = n/2;
   int j = -1;

   for (int i = 0 ; i < n-2 ; i ++ )
   {
      bool expectingNumber = (i % 2 == 0) ? true: false;

      if (expectingNumber)
      {
         if (j == -1) continue;
         char temp = a[i];
         a[i] = a[j];
         a[j] = temp;
      }
      else
      {
         if (j == -1)
         {
           j = k;
         }
         else if (j == i)
         {
            j++;
         }
         char temp = a[i];
         a[i] = a[k];
         a[k] = temp;
         k++;
      }
   }
}

public static void Interchange(char[] arr)
        {
            int i = arr.Length / 2;
            int k = i , j = 0;
            
            for (; i < arr.Length-1; ++i)
            {
                k--;
                for (j = i; j > k; j=j-2)
                {
                    char temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                   
                }
            }
            
        }

/* Assuming the First half of the array is in sorted order */
#include<stdio.h>
#define ARRAYSIZE 10
int main()
{

char array[ARRAYSIZE] = {'1','2','3','4','5','a','b','c','d','e'};
int i;
int value = 0;
int mid_index = ARRAYSIZE/2;
for(i=0;i<ARRAYSIZE;i++)
{
if(i%2 == 0)
{
value++;
array[i] = value + '0';
}
else
{
array[i] = array[mid_index];
mid_index++;

}
printf("Value of the Array at %d th index is : %c\n",i,array[i]);


}

return 0;

}

This looks like a matrix transpose. Given an index i the transpose index i' is computed as i' = (index % #cols) * #rows + (index / #cols). For example if i = 3 (a[3] = 4) then the transpose index is (3 % 5)*2 + (3 / 5) = 6. Likewise, if i = 7 (a[7] = c) then the transposed index is (7 % 5)*2 + (7/5) = 5. So given a function transpose(index) it is O(1) to compute the transpose index. Hence, there exist a O(n) algorithm to arrange this array.

protected int transpose(int index, int num_row, int num_col){
		return (index % num_col)*num_row + (index / num_col);
	}

The implementation of the in-placed sorting is only 10 lines and I wish to see this contribution from you guys.