CareerCup

Just encode each number with its index. (while decoding we can retain the actual number and present).

i.e. A[i] = i;(if A[i]>0) and
A[i] = -i; (if A[i]<0).

Now
i) Apply sorting on these numbers( in nlgn time)
ii)reverse the negative numbers(indices for now)
iii) Decode to get back the actual numbers and present.

So O(nlogn).
space - O(n) is straightward. O(1) space is possible, because we are only comparing indices which can be generated and compared on the fly, however we swap the actual number so we accomplish the need.

Ex: 1, 7, -5, 9, -12, 15
Array = 1, 7, -5, 9, -12, 15
Encode_Array = 0, 1, -2, 3, -4, 5.

Sort => -4, -2, 0, 1, 3, 5
Reverse neg portion => -2, -4, 0, 1, 3, 5.
Decode => -5, -12, 1, 7, 9, 15

using HASH table can be done in O(n) space and O(n) time.

if constraints are given then a variant of insertion sort can be used with the place value as the main sentinel and negative value as the landmark value. constant space , O(n2) worst case time

keep another array storing the index
sort the original array in nlgn
for positive and negative part, sort separately according to index

create another array ss
scan the original array oo, put the negative elements in oo to ss
scan the original array again, put the positive elements to ss

space O(n) time O(n)

Can this be done in O(1) space?

I guess the challenge here is O(n) time and O(1) space. Is this possible? Does anyone have any idears?

#include<stdio.h>
void arrange(int *a,int n)
{
int j=0,i;
for(i=0;i<n;i++)
{
j=i;
if(a[i]>0)
a[j++]=a[i];
else
{
if(a[j-1]>0)
{
int t=a[i];
while(j>0 && a[j-1]>0)
{
a[j]=a[j-1];
j--;
}
a[j]=t;
}
}
}
}

main()
{
int a[]={-1,1,7,-5,9,-12,15,78,-890,122},i;
printf("before\n");
for(i=0;i<10;i++)
printf("%d\t",a[i]);
arrange(a,10);
printf("\nafter\n");
for(i=0;i<10;i++)
printf("%d\t",a[i]);
printf("\n");
return 0;
}

i dont know wheather this is right.
its simple
try out with simple wits, it can be done in one pass of quick sort.
and its done.
ok ok i tell you more
1. take 2(up, down) pointers starting from different ends of the sequence.
2. for up < down
2.a inc. 'up' as long as numbers are negative
2.b dec [b]'down'[/b]as long as numbers are +tive
2.c if(up < down) swap [up] and [down]
end for

Joke's second algorithm is simple but requires a array of size n.
If n is not known first, it may have problem.
Since the original orders must retained. Applied the sorting algorithm does not make sence.

Here is an alogrithm of at most n/2 spaces and 2.5 n pass.

1. Scan the array A and record the first positive index(pIndex) and negative index(nIndex), also count the number of positives pNo and negative nNo.
2. Select the smaller of pNo and nNo, say we have nNo < pNo
3. Create an array B of size nNo. Start with A[nIndex], move that negative no to the first element of new array B[0] and set A[nIndex]=0. Now, check A[nIndex+1].
if it is positive, replace A[nIndex] with A[nIndex+1], and set nIndex = nIndex+1. If it is negative, move it to B[1] and set A[nIndex+1] =0. Suppose we see 4 negative no consecutively, we would have moved 4 negative no to B[0] to B[3]. And now A[nIndex+4] is positive. We then replace A[nIndex] with A[nIndex+4] and increase nIndex by 1.
4. In the end, we move all negative numbers to B and move all positive numbers to the first pNo elements of array A. The final step is move all negatives to the right side of A.

Divide and conqor. n* log(n).

There is a algorithm requires no extra space, but it is a O(n*n) algorithm(although it can be improved in most cases).

Give A[0] ... A[n], with both positive and negative numbers. To be simple, asumming A[0] > 0.
1. Check pairs A[0], A[1], since A[0]>0, do nothing. Go on to check A[2] and A[3]. If A[2] > 0, do nothing. If A[2]<0, two cases: A[3]>0, swap A[2] and A[3]; A[3]<0, do nothing. Continue to work every pairs up to A[n-1] and A[n] if n is odd(A[n-2] and A[n-1] if n is even.
2. Next, start with A[1] and A[2], re[eat the above steps. In every step, we move the negative numbers to the right side. It would end in at most n-2 iterations.

To improve the above algorithm, we do start at A[0]. We can scan the array and begin with the first i, that has A[i] < 0 and stop at some j that has A[j]>0 and A[j+k] <0 for k= 1,2, ....

Example:
1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
iteration 1:
A[2]=-5, A[3]=9 : swap A[2] and A[3];
A[4]=-12, A[5]=15 : swap A[4] and A[5] => 1, 7, 9, -5, 15, -12
Iteration 2:
A[3]=-5, A[4]=15 : swap them A[3]=15, A[4]=-5;
Do nothing with A[5] => 1, 7, 9, 15, -5, 12.

what about a simple and straight sln:

int ary[] = {1, 7, -5, 9, -12, 15 };
for(int i = 0; i < 6; i++ ) {
if(ary[i] < 0) {
for(int j = i; j > 0; j-- ) {
if(ary[j-1] < 0) break;
int temp = ary[j];
ary[j] = ary[j-1];
ary[j-1] = temp;
}
}
}
for(int i = 0; i < 6; i++)
cout<<ary[i]<<" ";

I guess it's better to use a modification of qsort approach
void divide(int* arr, int n)
{
int l = 0;
int r = n - 1;
int pivot = 0;
while (true)
{
while (a[l] < pivot) ++l;
while (a[r] > pivot) --r;
if (l >= r)
return;
swap (a[l], a[r]);
}
}

O(n) time and O(1) space

David is right, the solution is incorrect - sorry

distribute(A, p, r) // p =0 or start index of array r = last index of array

1 x ← 0
2 i ← p - 1
3 for j ← p to r
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] ↔ A[j]

Check this

void prob()
{
//int arr[]={1,7,-5,9,-12,15};
int arr[]={-1,1,7,-5,9,-12,15,78,-890,122};
int i=0;
while(i<9)
{
if(arr[i]>0 && arr[i+1]<0)
{
int k=arr[i];
arr[i]=arr[i+1];
arr[i+1]=k;
i=0;
}
else
{
i++;
}
}
for(int i=0;i<9;i++)
{
std::cout<<arr[i]<<std::endl;
}

Why not just take O(n) to look how many negative numbers at first. In the example. It is 2. So set two pointers i and j, i starts from 0 and j starts from 2. If array[i] is negative and array[j] is positive, do nothing, i++ and j++. If array[i] is positive and array[j] is negative, swap array[i] and array[j], i++,j++. If array[i] and array[j] are both positive, j++. If array[i] and array[j] are both negative, i++. Do it in O(n) and space complexity is O(1).

Can't we do simply the following:
1. Initialize a 'tracker' that keeps track of negative numbers present at the start of array.
2. Trace an entire array and whenever we find negative number at position 'pos', shift all the elements from 'tracer' to 'pos' and insert then negative number at 'tracer'.
3. It will take O(n^2).

http://wuhrr.wordpress.com/2008/01/11/find-largest-sum-of-contiguous-numbers-in-an-array/
This link gives the right solution

#include<stdio.h>

#define MAX 18 
#define Positive(x)  ( ((x)>0)?1:0 )

void Swap(int* a, int* b)
{
	int t = *a;
	*a = *b;
	*b = t ;
}
// 1 2 3 4 (-5 -6 -7 -8 -9) 10 11 -12 -13 -14 15 -16 17 
// 1 2 3 4 (-9 -8 -7 -6 -5) 10 11 -12 -13 -14 15 -16 17

int arr[MAX] = { -77, 1, 2, 3, 4, -5, -6, -7, -8, -9, 10, 11, 12, 13, 14, 15, -16, 17 };

// 1 2 3 4 (10 11 12 13 14) (-5 -6 -7 -8 -9) (15) -16 17

void print_arr(int* a)
{
	int i = 0 ;
  	for ( i = 0 ; i < MAX; i++)
	{
		printf("%4d",a[i]);
	}	
	printf("\n");
}
void rearrange( int* a,  int len )
{

	int SwapFound = 1 ;
	int i = 0 ;
	while ( SwapFound )
	{

		print_arr(a);
		fgetc(stdin);
		SwapFound = 0 ;
		for ( i = 0;  i < len-1 ; i++)
		{
			if ( !Positive (a[i]) && Positive(a[i+1] )   )
			{
				SwapFound = 1;
				Swap(&a[i], &a[i+1]);
			}	
		}
	}
}
int main()
{
       	rearrange(arr, MAX);
}

Consider this recursive algorithm which divides array into two subarrays and does rearrangement on them:

static int Rearrange(int[] arr, int l, int u)
        {
            if (l > u)
            {
                throw new ArgumentException();
            }

            if (l == u)
            {
                return arr[l] > 0 ? 1 : 0;
            }

            var m = (l + u)/2;
            var leftPositives = Rearrange(arr, l, m);
            var rightPositives = Rearrange(arr, m + 1, u);
            if (leftPositives > 0)
            {
                Swap(arr, m - leftPositives + 1, u - rightPositives, leftPositives);
            }
            return leftPositives + rightPositives;
        }

        static void Swap(int[] arr, int l, int u, int positiveCount)
        {
            if (l == u)
            {
                return;
            }

            var total = u - l + 1;
            var negativeCount = total - positiveCount;
            Array.Reverse(arr, l, positiveCount);
            Array.Reverse(arr, l + positiveCount, negativeCount);
            Array.Reverse(arr, l, total);
        }

no good solution yet!

- have two pointers, one point to first positive num, one point to first negative num
- swap them, advance both pointer to the next positive and negative num
- swap them, so on ...

time: o(n), space o(1)

Just encode each number with its index. (while decoding we can retain the actual number and present).

i.e. A[i] = i;(if A[i]>0) and
A[i] = -i; (if A[i]<0).

Now
i) Apply sorting on these numbers( in nlgn time)
ii)reverse the negative numbers(indices for now)
iii) Decode to get back the actual numbers and present.

time - O(nlogn).
space - O(n) is straightward. O(1) space is possible, because we are only comparing indices which can be generated and compared on the fly, however we swap the actual number so we accomplish the need.

Ex: 1, 7, -5, 9, -12, 15
Array = 1, 7, -5, 9, -12, 15
Encode_Array = 0, 1, -2, 3, -4, 5.

Sort => -4, -2, 0, 1, 3, 5
Reverse neg portion => -2, -4, 0, 1, 3, 5.
Decode => -5, -12, 1, 7, 9, 15

So basically, if space is O(1) time is O(n^2) [stable sort solution] or if space is O(n) time is O(n) [2nd solution by joke on January 11, 2009]. Please correct me if I am wrong.

This code runs like a charm. does it in O(n) time with O(n). There was no mention of not using extra space.

You have to use extra space in this case other wise you will have to shift cells to keep them in place which can never be O(n), efficient or simple

<pre lang="" line="1" title="CodeMonkey55110" class="run-this">// and here is the code

public static int[] PositiveNegative(int[] arr)
{
if (arr == null || arr.Length < 2)
return arr;

// get the number of negatives
int numberOfNegatives = 0;
for (int i = 0; i < arr.Length;i++ )
{
if (arr[i] < 0)
numberOfNegatives++;
}

// if there are no negatives return the original array
if (numberOfNegatives == 0)
return arr;

//With knowledge of new number of negatives we can create new array with arranged integers
int[] newArray = new int[arr.Length];
int negIndex = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] < 0)
{
newArray[negIndex]=arr[i];
negIndex++;
}
else
{
newArray[i + (numberOfNegatives-negIndex)] = arr[i];
}
}

return newArray;
}</pre><pre title="CodeMonkey55110" input="yes">
</pre>

public class sortarray {


public static void main(String[] args) {
int a[]={9,4,-3,-2,1,-1,5,7,-9,-5};
int k=0;
int l[]=new int[10];
for(int i=0;i<a.length;i++)
{
if(a[i]>0)
{
System.out.print(a[i]);

}

else
{
l[k]=a[i];
k++;

}

}
for(int i=0;i<k;i++)
{
System.out.print(l[i]);
}


}

}

See My Solution below

O(n) and O(1)
#include <stdio.h>
#include <stdlib.h>

void reverse(int a[],int i,int j);
int main(int argc, char *argv[])
{
int a[]={12,13,-14,-15,-16,-20,-30};

// 12,13,

int i =0;
int negative =0;
int reversenegative=0;
int temp =0;
for( i=0;i<=6;i++)
{
printf("%d ",a[i]);
}
for( i=6;i>=0;i--)
{
if(a[i]<0)
{

negative=negative+1;

}
else
{
temp=a[i];
a[i]=a[i+negative];
a[i+negative]=temp;
if(negative>1)
{
reversenegative++;
}
}

}

/*printf("Reverse Negative %d ",reversenegative);
printf("Negative Negative %d ",negative);*/




reverse(a,0,reversenegative-1);
reverse(a,reversenegative,negative-1);
reverse(a,0,negative-1);


printf("\n");
for( i=0;i<=6;i++)
{
printf("%d ",a[i]);
}
system("PAUSE");
return 0;
}


void reverse(int a[],int i,int j)
{
int temp;
while(i<j)
{
temp=a[j];
a[j] =a[i];
a[i]=temp;
i++;
j--;
}
}

soln won't work for some cases. Workin to fix the problem .ignore my soln till then