Write an algorothm to find the position of rightmost set bit in binary representation of number

Example

Number 19,   Binary Representation 010011
Answer Position of right most set bit 1

Here is an order of log(X) algorithm. We can conclude from 2's complement form that "a number can be converted to 2's complement form by complementing each bit from right most set bit". For example, -7 can be obtained in the following way (assuming 8 bit size)

8 = 00001000
-8 = 11111000

If we perform ANDing between x and -x we left with right most set bit. All this takes O(1) time. Now use binary search [ O(log(x)) ] to figure out which bit is set. Given below is code.





int getPosition(unsigned x)

{

    // ASSUMPTION: x will not be zero



    // left, right and mid position

    int l = 0, r = 33, mid = 0;

    // temp value

    unsigned temp;



    // Iterate till we find the bit position

    while(l < r)

    {

        // ((r - l) >> 1) + l - Is more effective??

        mid = (l + r) >> 1;



        // Set the most possible significant bit

        temp = (1 << (mid - 1));



        if(temp == x)

        {

            break;

        }

        else if(temp < x)

        {

            // Bit is in the higher half

            l = mid;

        }

        else

        {

            // Bit is in the lower half

            r = mid;

        }

    }



    // Return mid itself if bits

    // are positioned from 1 to 32

    return (mid-1);

}



int getRightMostSetBit(unsigned x)

{

    // Return 0 if x is zero

    int position = 0;



    // Avoid multiple return statements

    if(x != 0)

    {

        // Make the integer passes as least power of 2

        // Call the position locator

        position = getPosition(x & -(signed)x);

    }



    return position;

}



Source Heard from My Friend Venki

WAP to find Kth Maximum or Largest in Binar Search Tree (BST)

class BST  

{
 private static Node root;
  
 public static void main(String [] args) {
  int [] A = {8, 3, 10, 1, 6, 14, 4, 7, 13};
  root = buildBST(root, A);
  System.out.println("inorder: ");
  printBSTInorder(root);
  System.out.println();
  int sizeBST = sizeOfBST(root);
  System.out.println("Size of BST: " + sizeBST);
   
  for (int i=1; i<=sizeBST; i++) {
   Node node = nthLargestNode(root, i);
   System.out.println(i + " largest node: " + node.data);
  }
 }
  
 public static Node nthLargestNode(Node node, int N) {
   if (null == node) 
  {
   return null;
  }
    
  int R = sizeOfBST(node.right) + 1;
  if (N == R) 
  {
   return node;
  }
  if(N < R) 
  {
   return nthLargestNode(node.right, N);
  } 
  else 
  {
   return nthLargestNode(node.right, N-R);
  }
  }
 
  
 public static int sizeOfBST(Node node) {
  if (null == node) { return 0; }
  return (sizeOfBST(node.left) + 1 + sizeOfBST(node.right));
 }
  
 public static Node buildBST(Node node, int [] A) {
  if (A == null) { return null; }
  int len = A.length;
  for (int i=0; i<len; i++) {
   node = insertIntoBST(node, A[i]);
  }
  return node;
 }
  
 private static Node insertIntoBST(Node node, int value) {
  if (null == node) {
   return new Node(value);
  }
  if (value <= node.data) {
   node.left = insertIntoBST(node.left, value);
  } else {
   node.right = insertIntoBST(node.right, value);
  }
  return node;
 }
  
 public static void printBSTInorder(Node node) {
  if (null == node) {  return ; }
  if (null != node.left) {
   printBSTInorder(node.left);
  }
  System.out.print(node.data + " ");
  if (null != node.right) {
   printBSTInorder(node.right);
  }
 }
}
 
class Node {
 Integer data;
 Node left;
 Node right;
  
 public Node(Integer data) {
  this.data = data;
  this.left = null;
  this.right = null;
 }
}

 Run Here http://ideone.com/rUQbn

 Time Complexity O(N^2) N is number of nodes in BST

 Space Complexity O(1)   Ping me if anything wrong here  

find degree of connection of two users in social networking site, like linkedin shows us upto 3rd level degree of distance

find degree of connection of two users in social networking site, like linkedin shows us upto 3rd level degree of distance.so the aim is to find minimum degree of connection between two users.
by degree of connection i mean, say user1 is friend with user2 and user2 is also friend with user3
now user1 and user3 are 1st degree of connection with user2
and user3 is 2nd degree of connection with user1