Wednesday, September 12, 2007

Solution:
------------

let a and b be given nos ( or values of given nodes )

common_ance( node )
{
........if( ( a <node && b > node ) || ( a > node && b < node ) || a == node || b== node)
........ return node

........else if ( a < node && b < node )
........ return common_ance( node - > left )

........ else
........ return common_ance ( node -> right )
}

initial call is common_ance( root )

Psudocode:
----------------

first condition checks if given nodes lie in left n right subtrees of root
if yes return root
else
if both lie in left subtree then call common_ance( root -> left )
else common_ance ( root - > right )


Powered by ScribeFire.

Division with using /,% operator

Question:
--------------

Two integers a, b how to divde a/b without using /,% operator... (repeted subtraction is not the solution).

Solution:
-----------

#include<stdio.h>
int main()
{
printf("%d\n", divide(40,2));
return 0;
}

int divide(int num, int denom)
{
int a=0, b=0;
int i= 31; // CAREFUL: works only on int=32-bit machine!
/* Work from leftmost to rightmost bit in numerator */
while(i>=0) {
/* appends one bit from numerator to a */
a = (a << 1) + ((num & (1 << i)) >> i);
b = b << 1;
printf("After shifting a=%d and b=%d\n",a,b);
if (a >= denom) {
a -= denom;
b++;
}
printf("After subtraction a=%d and b=%d\n",a,b);
i--;
}
return b;
}




Powered by ScribeFire.

Sunday, September 09, 2007

One of the site which I came across

http://www.tekpool.com/?cat=9