Anurag Singh
BAN USEROR even better, Use hash table.
Iterate through the array and insert elements in hash table (Don't insert in case of collision i.e. duplicates).
Hash table size is the answer.
Time: O(n), Space: O(n)
if range of array element known (Say max no is n) Use index array say idx of size n, set to ZERO.
Iterate through given array a and set idx as idx[a[i]]++;
Count of 1 in idx is the answer. Time: O(n), Space: O(max array value).
Will take more space if range is high (And array values are sparse)
Otherwsie:
Use BST/AVL etc (As Mike said)..
Keep inserting in Tree if it is not there already (Don't insert duplicates)
and keep track of tree size.
At the end, Tree size is the answer.
Time: O(n log n), Space: O(n)
x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); //Only this line if 2 bits can represent the integer
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2); //This and all above if 4 (or less) bits can represent the integer
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4); //This and all above if 8 (or less) bits can represent the integer
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8); //This and all above if 16 (or less) bits can represent the integer
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16); //This and all above if 32 (or less) bits can represent the integer
So all above four lines can be used for any integer (32 bit integer)
For input 1001101 i.e. decimal 77, 1st three lines will give the result as input can be taken as 8 bits (01001101), so after 3rd line of execution, value of x will be:
10110010
Create Suffix Tree for the given string, then search for any substring in that.
- Anurag Singh January 27, 2011Insertion Sort using Recursive Push
1. pop top element from S1
2. Find the right place for it in S2 and push the element
2.1 If S2 is empty, push element in S2
2.2 If not empty, keep popping elements from S2 until right place for element is
found, then push this element, then push all other popped element back in S2
Time: O(n2), Space: O(1)
void main()
{
Stack S1, S2;
if(isEmptyS(S1) return;
push(S2,pop(S1));
while(!isEmptyS(S1)
{
recursivePush(S2,pop(S1));
}
//Printing S2, which is sorted now (non-decreasing)
while(!isEmptyS(S2)
{
printf("%d ",pop(S2));
}
}
void recursivePush(Stack S2, int element)
{
int tmp=0;
if(!isEmptyS(S2) && tmp > top(S2))
{
tmp=pop(S2);
recursivePush(S2,element);
push(S2,tmp);
}
else
push(S2,element);
}
In one pass:
1. Take two pointers, slow and fast, both pointing to head of list
2. Now move slow point node node next and fast pointer two node next
3. Keep moving until fast pointer reaches to END of list OR 2nd last node (depends on node count in list is odd or even), at this point, slow pointer is at the center of list.
#include <stdio.h>
int main(int argc, char *argv[])
{
int xor=0;
int i, x=0, y=0;
int len=10;
//Taking range as 1-10 where 4 and 7 are missing
int a[10] = {1,2,3,5,6,8,9,10};
//This is XOR of given array elements and all elements in the range
for(i=0;i<len-2;i++)
{
xor ^= a[i];
xor ^= (i+1);
}
xor ^= (len-1);
xor ^= len;
//Get the position of first rightmost (LSB side) bit set in xor
int p = 0;
while(xor)
{
if(xor&1)
break;
else
{
p++;
xor >>= 1;
}
}
printf("p=%d\n",p);
//Divide all elements into 2 sets and take XOR of them
for(i=0;i<len-2;i++)
{
if(a[i] & 1 << p)
x ^= a[i];
else
y ^= a[i];
if((i+1) & 1 << p)
x ^= (i+1);
else
y ^= (i+1);
}
if((len-1) & 1 << p)
x ^= (len-1);
else
y ^= (len-1);
if(len & 1 << p)
x ^= len;
else
y ^= len;
printf("x=%d y=%d\n",x,y);
return 0;
}
Using XOR,
1. XOR all element given in array (98 in count) AND also numbers 1 to 100.
2. Resultant XOR will be the XOR of two missing elements (x^y)
3. Get the position of first rightmost (LSB side) bit set in above result, say it is 2nd position.
4. Divide all elements (array elements and the range elements) in two sets.
5. 1st set will have all elements where 2nd bit is ZERO. XOR of all these elements in this set will one missing value.
6. 2nd set will have all elements where 2nd bit is ONE. XOR of all these elements will give 2nd missing value.
n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1); //Only this line if 2 bits can represent the integer
n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2); //This and all above if 4 (or less) bits can represent the integer
n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4); //This and all above if 8 (or less) bits can represent the integer
n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8); //This and all above if 16 (or less) bits can represent the integer
n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16); //This and all above if 32 (or less) bits can represent the integer
So all above four lines can be used for any 32 bit integer.
x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); //Only this line if 2 bits can represent the integer
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2); //This and all above if 4 (or less) bits can represent the integer
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4); //This and all above if 8 (or less) bits can represent the integer
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8); //This and all above if 16 (or less) bits can represent the integer
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16); //This and all above if 32 (or less) bits can represent the integer
So all above four lines can be used for any integer (32 bit integer)
wrapper classes in java.lang package are immutable.
i.e.
Integer, Long, Short, Float, Double, Boolean, Byte, Character, String
Using Level Order Traversal (using Queue)
Added null after all nodes in one level are added in queue, as an indicator of one level traversal
int min_depth(BT t)
{
int depth=0;
Queue q;
if(!t || (!t->left && !t->right))
return 0;
Enqueue(Q,t);
Enqueue(q,null);
while(!IsEmptyQ(q))
{
node=Dequeue(q);
if(q==null)
{
depth++;
if(!IsEmptyQ(q))
Enqueue(q,null);
}
else
{
if(!t->left && !t->right)
return depth;
else
{
if(t->left)
Enqueue(q,t->left);
if(t->right)
Enqueue(q,t->right);
}
}
}
}
Added null after all nodes in one level are added in queue, as an indicator of one level traversal
int min_depth(BT t)
{
Queue q;
Enqueue(Q,t);
Enqueue(q,null);
while(!IsEmptyQ(q))
{
node=Dequeue(q);
if(q==null)
{
printf("\n");
if(!IsEmptyQ(q))
Enqueue(q,null);
}
else
{
printf("%d ",node->data);
Enqueue all childs of node in q;
}
}
}
If we need to print all nodes in a single line,
e.g. 1 2 3 4 5 6 7 8
both of above are correct, so better to go with only one Queue.
But to print nodes as dxcrazy said:
1
2 3 4
5 6 7 8
Above won't work.
This is a working solution but it does complete tree traversal. Level order traversal would be more efficient which is below after few other posts.
- Anurag Singh January 23, 2011
Good One !!!
- Anurag Singh January 28, 2011