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

You have to count how many binary strings are possible of length "K". Constraint: Every 0 has a 1 in its immediate left. 111011 <-- valid 0111 <--- invalid 111100 <-- invalid

d cube root of number without using any library function number can be as large as 10^1000

Count no of different places tommy can cover from home to school condition is one place can't be visited twice and after reaching school he can't proceed further.

Tommy reach school frm his home there are many places b/w their home and school connected by bidirectional paths u have to count no of different places he can cover from home to school condition is one place can't be visited twice and after reaching school he can't proceed further.
you have
given:-
Input
t
n m h s
m lines
Output:
count
t is  number of test case
n is number of nodes,m id number of bidirectional path, h is home and s is school
m lines bidirectional path b/w nodes x and y.
out put count is number of different nodes he can go from school satisfying the condition.
Sample Input:
1
3 3 0 1
0 1
1 2
0 2
Sample Output:
3

Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers

#define ARR_SIZE 100
#include<stdio.h>


void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}


/* The function prints all combinations of numbers 1, 2, ...n
that sum up to n. i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int n,int m ,int i)
{

/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
static int arr[ARR_SIZE];

if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= m; k++)
{
arr[i]= k;
printCompositions(n-k,m, i+1);
}
}
}


/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 , 3 , 4 and 5  %d are\n", n);
printCompositions(n,n, 0);
getchar();
return 0;
}

Time Complexity O(n^m) Exponential
Space Complexity O(m)
Run Here http://ideone.com/clone/ETZTv

find the number of maximal squares that can be formed. A square is formed by grouping adjacent cells containing 1. A maximal square is one that is not completely contained within another square. Maximal squares that overlap partially are to be counted separately

Given a matrix of order M x N containing 1.s and 0's, you have to find the number of maximal squares that can be formed. A square is formed by grouping adjacent cells containing 1. A maximal square is one that is not completely contained within another square. Maximal squares that overlap partially are to be counted separately. Unit squares (length of side = 1) should be also counted.
Note that squares are filled, i.e. they cannot contain 0.s.

Number of maximal square: 6
Input specification:
The first line consists of integers M and N, the number of rows and columns of the matrix.
0 < M and N <=40
Next M lines contain N characters from the set {0, 1}.
Output specification:
An integer representing the number of maximal squares that can be formed followed by a newline.
Sample Input and Output:

Input:
4 5
11001
11110
11011
11001

Output:
9

Input:
2 2
10
11

Output:
3

Source: Heard From user Bhavesh