CareerCup

Just put the characters in place first. So for every position in the array 1,3,5,... and so on, just place the characters c1,c2,c3 by exchanging the values of the integers in those positions by the character positions.

After this, you will have the array with all the characters at right positions, but the integers will be randomly distributed. Use modified quicksort on adjacent positions (0,2,4,6...) of the array to sort the integers.

The running time of the algo is O(n + nlgn) = O(nlgn)

another simple solution that works in O(n) time.

Traverse the array and find the right location. Eg: if an element is located at position 2 (array starts at 0) its right position would be 2*2 mod maxIndexofArray = 4. Replace the value at position 4 and and find the right position for this new element. Keep track of the start index to make sure we dont do into an infinite loop. Get the next untouched element and repeat.

pseudo code:
startIndex,curIndex =0; maxIndexofArray=lenghtofArray-1;
while (curIndex != maxArrayofIndex)
{
 do {
     curIndex = curIndex*2;
     curVal = array[curIndex];
     array[curIndex] = prevVal;
     prevVal = curVal;
 }while (curIndex != startIndex)
 curIndex = (curIndex *2) + 1
 startIndex = curIndex;
 prevVal = array[curIndex];
}

Above solutoin has a bug... curIndex should be incremented.,

void in_place_rearrange(int arr[], size_t n){
int temp1=arr[1];
int temp2=-1;
size_t index=1;
size_t start=1;
for(int i=1;i!=2*n-1;++i){
if(index<n){
index=index*2;
}else{
index=2*(index-n)+1;
}
temp2=arr[index];
arr[index]=temp1;
temp1=temp2;
if(index==start){
for(size_t j=start;j!=2*n-1;++j){
if((arr[j]+j)%2!=1){
index=j;
temp1=arr[j];
break;
}
}
}
}
};

Note that the first and the last values never change their position. So, we have to deal with 2n-2 values.

Integers at index i, should end up at j = 2*n. Similarly, characters at index i, should end up at j = 2*n+1.

With the above information, we start with the second index of the array and determine its correct position in the final array. The old value at this position is recorded along with its index, which is used in the next iteration. We perform this 2n-2 times to ensure all elements end up in their final positions.

int count = 0;
int i = 2;
int j, tmp = a[i], tmp1;

while (count < 2*n-2)
{
count++;

if (i < n)
j = 2*i;
else
j = 2*i+1;

tmp1 = a[j];
a[j] = tmp;
tmp = tmp1;
i = j;
}

array with int and char together???? what kind of array is it???
array is a collection of similar data types...BASICS :)

Anonymous has raised a valid question. I think instead of chars we can assume that we have different set of numbers and focus on the logic of pairing up things in the required manner.

Consider the following example where n(=12) is an even number
e.g. 1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l

step 1: for the first n part do not move the even positioned elements and for the next n part do not move the odd positioned elements.(i.e. 1_3_5_7_8_9_11_ _b_d_f_h_j_l) but interchange the even positioned elements of the first n part with the odd positioned elements of the second n part which results into the following sequence. 1 a 3 c 5 e 7 g 9 i 11 k 2 b 4 d 6 f 8 h 10 j 12 l, which can be viewed as pairs indicated below
(1 a) (3 c) (5 e) (7 g) (9 i) (11 k) (2 b) (4 d) (6 f) (8 h) (10 j) (12 l)

Step 2: Apply the same pairing logic as described above fix the odd positioned pairs in the first n-element array and even positioned elements in the second n-element array and exchange the rest will result into the following

(1 a) (2 b) (5 e) (6 f) (9 i) (10 j) (3 c) (4 d) (7 g) (8 h) (11 k)(12 l)

Now this can be viewed by pairing up four elements togeher in the following way

(1 a 2 b) (5 e 6 f) (9 i 10 j) (3 c 4 d) (7 g 8 h) (11 k 12 l)

step 3: Do the same thing like fixing the odd positioned elements in first half and even positioned in the second half and exchange the rest

(1 a 2 b) (3 c 4 d) (9 i 10 j) (5 e 6 f) (7 g 8 h) (11 k 12 l)

step 4: Pair up the adjacent elements again to result into the following

(1 a 2 b 3 c 4 d) (9 i 10 j) (5 e 6 f 7 g 8 h) (11 k 12 l)

step 5: Apply the same logic again and you will end up with the result
(1 a 2 b 3 c 4 d 5 e 6 f 7 g 8 h 9 i 10 j 11 k 12 l)

Logic needs to be changed a little bit in when n = odd number and I am working on it.

But there is a lot of overhead of exchanging elements if anybody can come out with some insight to overcome this pls discuss it. Thank you.

void alternateIntChar()
{
	vector<char> vc;
	char i;
	for( i = 0; i < 10; i++)
		vc.push_back(i+'0');
	for(i=0;i<10;i++)
		vc.push_back(i+'a');
	cout << "Before: "<< endl;
	vector<char>::iterator it;
	for(it=vc.begin(); it != vc.end(); ++it)
		cout << *it << ",";
	vector<char>vo;
	for(i=0;i<vc.size()/2;i++)
	{
		vo.push_back(vc[i]);
		vo.push_back(vc[i+10]);
	}
	cout << "After: " << endl;
	for(it=vo.begin(); it != vo.end(); ++it)
		cout << *it << ",";

}

// PairUp.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <iostream>
using namespace std ;

int LEN ;

//int arr[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 3, 5, 7, 9, 11, 13, 15, 17, 19 } ; //With n=5
/* 0 1 2 3 4 5 6 7 8 9
* result = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
* */

static int count = 0 ;

int * CreateArray(int N )
{
int* arr = new int[2*N] ;
for ( int i = 1 ; i <= 2*N; i++)
{
if ( i <= N )
{
arr[i-1] = i*2 ;
}
else
{
arr[i-1] = (i-N)*2 +1 ;
}
}
return arr ;
}

void PrintArray(int*arr)
{

for (int i = 0 ; i < LEN*2 ;i++)
{
cout<<arr[i]<<" " ;
}
cout<<endl;
}

void Swap(int* a, int*b)
{
int t = *a;
*a = *b;
*b = t ;
}

//Assume that array length is 2n
//Assume that the array contains a_1, a_2, ..., a_n, b_1, b_2, ...b_n
//we need to give the output as (a_1,b_1), (a_2,b_2),...(a_n,b_n)



void PairUp(int* arr,int start, int end)
{

if (end - start <= 2 )
{
return ;
}
else
{

PrintArray(arr) ;
int mix = start + (end - start )/2 - 1 ;
Swap(&arr[mix], &arr[mix+1] );

count++ ;

PrintArray(arr) ;

for ( int i = 0 ; i < (end - start)/2 - 2 ; i++ )
{
Swap( &arr[mix-1-i],&arr[mix-i]) ;
Swap( &arr[mix+1+i],&arr[mix+2+i]) ;
PrintArray(arr) ;
count+=2 ;

}
PairUp(arr, start+2, end -2 );

}

}
int main(int argc, char** argv)
{
LEN = atoi(argv[1]) ;

int* arr = CreateArray(LEN);

PairUp(arr, 0, LEN*2 );
cout<<"----------count------"<<count<<endl ;

delete[] arr;

return 0;
}

using System;
using System.Collections.Generic;
using System.Text;

namespace alternate
{
class Program
{
static int length;
static void swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}

static int GetCorrectPosition(int pos)
{
if (pos <= length /2)
{
return 2 * pos - 1;
}
else
{
return (pos - length/2) * 2;
}
}

static int count;
static void alternate(ref int[] arr)
{
for (int i = length / 2; i > (length/4); i--)
{
int start = i;
int new_pos = GetCorrectPosition(start);
while (true)
{
++count;
swap(ref arr[new_pos], ref arr[start]);
int temp = new_pos;
new_pos = GetCorrectPosition(new_pos);
if (start == new_pos)
break;
}

if (count >= length/2)
break;
}
}
static void Main(string[] args)
{
int[] arr = { 0, 1, 3, 2, 4};
length = arr.Length - 1;
alternate(ref arr);
Console.WriteLine(count);
}
}
}

arr[i1, i2, i3, ... in, c1, c2, c3, ... cn]
We need two extra int variables(Is not this allowed in terms of in-place algo? Sorry and please ignore this answer if that is not allowed).
tempInt, tempPosition are those two variables.
1) i1 is not touched.
2) tempInt = arr[1];
3) arr[1] = arr[n];
4) tempPosition = n;
5) arr[n] = arr[i];
6) tempInt = arr[2];
7) arr[2] = arr[tempPosition];


keep doing this.
O(n) and n+2 space is needed

The correct answer without the temporay array. Cheers.

void Shuffle(int *pData, int mid, int size)
{
  if(size > 2)
  {
    for(int index = (mid & 1) ? mid + 1 : mid; index < size; index += 2)
    {
      int temp = pData[index];
      pData[index] = pData[index / 2];
      pData[index / 2] = temp;
    }
    for(int index = 2 * (mid - 1) - 1; index >= mid; index -= 2)
    {
      int indexF = mid - 1;
      for(int indexS = index; indexS >= mid; indexS -= 2)
      {
        int temp = pData[indexF];
        pData[indexF--] = pData[indexS];
        pData[indexS] = temp;
      }
    }
    int newMid = (mid & 1 ? mid + 1 : mid) / 2;
    Shuffle(pData, newMid, mid);
  }
}

  int tArray[] = {1,2,3,4,5,6,7,8,9,21,22,23,24,25,26,27,28,29};
  Shuffle(tArray, 9, 18);
  for(int i = 0; i < 18; i++)
    cout << tArray[i] << " ";
  cout << endl;

just go to mid of the array.
try swapping the numbers as follows.
initial:123abc
go to mid swap mid & mid+1
12a3bc
2 recursive calls
one to i-1
so it swaps i-1 and i
other to i+1
so it swaps i+1 and i+2
1a2b3c
check for boundary conditions...
here u need one temp variable for swapping ..

this can be done with much ease:

say you have a1,a2,a3,a4,b1,b2,b3,b4
you can do it with an example :a1,a2,a3,a4,b1,b2,b3,b4
start with the middle pair of elements as follows :
now swap 1 pair : a1,a2,a3,[a4,b1],b2,b3,b4 ->a1,a2,a3,b1,a4,b2,b3,b4
now swap 2 pairs :a1,a2,[a3,b1],[a4,b2],b3,b4->a1,a2,b1,a3,b2,a4,b3,b4
now swap 3 pairs : a1,[a2,b1],[a3,b2],[a4,b3],b4->a1,b1,a2,b2,a3,b3,a4,b4
so if you have more number of elements obviously more swaps.

i1 i2 i3 i4 i5 i6 i7 i8 c1 c2 c3 c4 c5 c6 c7 c8//swap i5-i8 with c1-c4

i1 i2 i3 i4 c1 c2 c3 c4 i5 i6 i7 i8 c5 c6 c7 c8//swap i3,i4 with c1,c2,swap c5,c6 with i7,i8

i1 i2 c1 c2 i3 i4 c3 c4 i5 i6 c5 c6 i7 i8 c7 c8//swap i2 with c1, swap i4 with c3 ........

i1 c1 i2 c2 i3 c3 i4 c4 i5 c5 i6 c6 i7 c7 i8 c8

so we do the swap like binary sorting, the complexity is O(nlogn)

int* rearrange(int A[],int length)
{
int binary=1;
length=length/2;
while(length>1)
{
for(int m=0;m<binary;m++)
{
	for(int n=0;n<length/2;n++)
	{
		int temp=A[(2*m+1)*length-length/2+n];
		A[(2*m+1)*length-length/2+n]=A[(2*m+1)*length+n];
		A[(2*m+1)*length+n]=temp;
	}
}
binary=binary*2;
length=length/2;
}
return A; 
}

None of the in-place solutions which claim O(N) time are correct. What kind of discussion is this?

'spt' suggested a good method.. My solution is inspired from him.. It takes O(n) time and 1 extra varaible..

Algo-

Consider array[] from 1 to n instead of o to n-1 (easy for calculation and understanding)


//Error checking..
if(n%2==1 || n <2)
return error;

int a = i2;

While (1)
{
if (a == integer)
//Calculate correct postn and store in postn
else
// calculate correct postn and store in postn

if(postn==2)
break;

Swap array[postn] and a
}



You have an answer ;-)

Sorry coder, your solution is wrong too.

for i = 1 to 2*n-1 step 2
....CircularRotate(A,i,(i-1)/2 +n)

Example :
<abcde12345>
<a1bcde2345> after CircularRotate(A,1,5) ( 5 shifts)
<a1b2cde345> after CircularRotate(A,3,6) ( 4 shifts)
<a1b2c3de45> after CircularRotate(A,5,7) ( 3 shifts)
<a1b2c3d4e5> after CircularRotate(A,7,8) ( 2 shifts)

for i = 1 to 2*n-1 step 2
....CircularRotate(A,i,(i-1)/2 +n)

Example :
<abcde12345>
<a1bcde2345> after CircularRotate(A,1,5) ( 5 shifts)
<a1b2cde345> after CircularRotate(A,3,6) ( 4 shifts)
<a1b2c3de45> after CircularRotate(A,5,7) ( 3 shifts)
<a1b2c3d4e5> after CircularRotate(A,7,8) ( 2 shifts)

CircularRotate(A,i,j)
{
char temp=a[j];
while(j>i)
a[j--]=a[j-1];
a[j]=temp;
}

YetAnotherCoder, your algorithm is O(n^2), isn't it?

i think posible's solution is correct..ne comments ??

possible's solution is O(n^2) even if correct.

There is an easy O(nlogn) solution and supposedly O(n) is also possible.

An O(n logn) time algorithm uses divide and conquer, and the following problem:

Given an array a[1..n], give an algorithm to do an inplace cyclic shift in O(n) time.

1 2 3 4 5 c1 c2 c3 c4 c5 - array
0 1 2 3 4 5 6 7 8 9 - current positions
0 2 4 6 8 1 3 5 7 9 - position where it should be placed

start from 1st position
copy the value to temp
see where it should be placed( position 2)
now swap the value at temp and position 2
now again check for where the 2nd element should be place(new position 4) go to position 4 and swap with temp. keep doing this till you come back to position 1.

This is O(n) solution

To get the new position if current position is less than n/2 do 2*i
if current position >= n/2 do 2*i/(n-1)

1 2 3 4 5 c1 c2 c3 c4 c5 - array
0 1 2 3 4 5 6 7 8 9 - current positions
0 2 4 6 8 1 3 5 7 9 - position where it should be placed

start from 1st position
copy the value to temp
see where it should be placed( position 2)
now swap the value at temp and position 2
now again check for where the 2nd element should be place(new position 4) go to position 4 and

swap with temp. keep doing this till you come back to position 1.

This is O(n) solution

To get the new position if i less than n/2 do 2*i
if i > n/2 do 2*i/(n-1)

666, It might be O(n) algorithm, but it gives the wrong answer.

For most n, you don't even touch all elements. You have the code, try it out for n = 10 to 20 say.

the O(n) algorithm without a temp array has a problem, when you move an element to its future place, and then move the element at that place to its future place, ..., until you reach the start place. that is one cycle.
However, one cycle may not cover all elements in the array. some elements are not moved. how to know if some elements are not moved and who they are, that's the problem? we only have constant space to resolve this problem.

http://mathworld.wolfram.com/Out-Shuffle.html

let n1 n2 n3 n4 c1 c2 c3 c4 be the array..
let us call it num and ch arrays each having 4 elements..
we will swap the last (n=4)/2 elements of num with the first n/2 elements of char
so two new array becomes n1 n2 c1 c2 and n3 n4 c3 c4..n=2
divide and conquor...
O(log n)
this will wrk out for even n's only ..
for odd n's..
n1 n2 n3 c1 c2 c3 suppose..
we willhave to move c1 to n2 using shifting....
n1 c1 | n2 n3 c2 c3...
now apply the prev method on second array,...
(nlogn)

here is a simple solution.

1)consider the array as 2 arrays each with size n/2.
2)create another array of size n
3)copy i1,c1,i2,c2,...
4)copy them back to the original array