srdjan
BAN USERfunction balanced(Node *root){
if (root == NULL)
return 0;
int left = balanced (root->left);
int right = balanced (root->right);
if (left == -1 || right == -1) // if any subtree is unbalanced
return -1;
else if (abs (left-right) <= 1) // this subtree is balanced
return left+right+1; // return number of nodes
else {
return -1;
}
}
Complexity : O(n)
- srdjan December 25, 2013Here is an O(n) solution without extra space.
void sort(int array[]){
int pos_p = -1;
int num_n = 0;
for(int a:array)
if(a<0) num_n++;
for(int i=0;i<array.length;i++){
if(array[i]>0){
if(pos_p == -1)
pos_p = i;
else
if(num_n > 0)
swap(array, i, pos_p);
}else{
num_n--;
if(pos_p >= 0){
swap(array, i, pos_p);
if(num_n>0)
pos_p = i;
else
pos_p = -1;
}
}
}
}
void swap(int array[], int i, int j){
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
public void printSubSets(int n[], int k){
HashSet<Integer> set = new HashSet<>();
int mask = (1 << n.length);
for (int i = 1; i < mask; i++){
int sum = 0;
for (int j = 0; j < n.length; j++){
if ((i & (1 << j)) > 0){
sum+=n[j];
set.add(n[j]);
}
}
if(sum>=k){
System.out.println(set);
}
set.clear();
}
}
Bitwise and shift operators are not endian dependent. Use that
- srdjan May 22, 2014