CareerCup

Its O(n^2).

This works. But dont know if this is O(n) or not.

The following uses extra space, but running time in only O(n). Any comments?

private static int[] sortarrayintonegativezeropositive(int a[],int size){
		int[] sorted=new int[size];
		
		int[] positives=new int[size];
		int[] negatives=new int[size];
		int zerocount=0;
		int positivecount=0;
		int negativecount=0;
		
		for(int i=0;i<size;i++){
			if(a[i]==0)
				zerocount++;
			else if(a[i]>0){
				positives[positivecount++]=a[i];
			}
			else{
				negatives[negativecount++]=a[i];
			}	
		}
		
		int count=0;
		for(int i=0;i<negativecount;i++){
			sorted[count++]=negatives[i];
		}		
		for(int i=0;i<zerocount;i++){
			sorted[count++]=0;
		}		
		for(int i=0;i<positivecount;i++){
			sorted[count++]=positives[i];
		}
		
		return sorted;
	}

The following sorts the matrix. To find 'kth' element, the add a check to stop the while loop at ctr==k.

private static int[] sortMatrix(int a[][],int rows,int cols){
		int elem[]=new int[rows*cols];
		
		int r1=0,c1=0,r2=0,c2=1,count=0;
		while(c1<cols && c2<cols){
			if(a[r1][c1]<a[r2][c2]){
				elem[count]=a[r1][c1];
				r1++;
			}
			else{
				elem[count]=a[r2][c2];
				r2++;
			}
			if(r1==rows){
				r1=0;
				c1=c2+1;
			}
			if(r2==rows){
				r2=0;
				c2=c1+1;
			}
			count++;
		}
		elem[count]=a[rows-1][cols-1];
		return elem;
	}

Here's a recursive approach. Assuming column 0 is A. and so on.

private static String getStringRepresentation(int num){
		char[] A={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
		StringBuilder output=new StringBuilder();
		
		if(num<26){
			output.append(A[num]);
			return output.toString();
		}
		int tmp=(num/26)-1;
		int rem=num%26;
		if(tmp<26){
			output.append(A[tmp]);			
		}
		else{
			output.append(getStringRepresentation(tmp));
		}
		output.append(A[rem]);
		
		return output.toString();
	}

For every row/column, maintain a field called SUM. When player 1 marks, add 2 to the sum, when player2 marks, add 5 to the sum. If the sum ever reaches 2*N, then player 1 win, If the sum reachers 5*N, then player 2 wins. We only need to check/update the sum for the row/column where the last player has played.

Note: instead of 2,5 we can use any two numbers which are relatively prime.