cijo.thomas
BAN USER
This works. But dont know if this is O(n) or not.
- cijo.thomas October 27, 2012The 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.
Its O(n^2).
- cijo.thomas October 31, 2012