circular rotation or cyclic shifts of bits in a given number

Problem link
https://www.hackerearth.com/practice/basic-programming/bit-manipulation/basics-of-bit-manipulation/practice-problems/algorithm/lets-shift-2-36d90caa/description/


PseudoCode:

        if(c == 'R')
       {
            while(m--)
           {
                if(n%2== 0)                  // if n is even the units bit/LSB will be 0 so this 0 will become MSB
                        n= n / 2;                   // right shift means dividing by 2
                else
                       n=(n+65535)/2;       // if n is odd, LSB will be 1 and after rotation this 1 becomes MSB
            }
        }
        else
       {
             while(m--)
               {
                      n = n* 2;                  //left shift means multiplication by 2
                      if (n>65535)           // in 16 bits the largest number that can be stored is 65535
                            n = n - 65535;   //as it is rotation after 65535 it becomes 1,2,3,4,5 ............
               }
       }
               

Hashing Using Separate Chaining: Java Program

import java.util.Scanner;

class SLLNode

{

      int data;

      SLLNode next;

}

class SeparateChaining

{

      SLLNode htable[];

      int tableSize;

      public void insert(int key)

      {

            int index=key%tableSize;

            SLLNode newnode=new SLLNode() ;

            newnode.data=key;

            newnode.next=null;

            if(htable[index]==null)

                  htable[index]=newnode;

            else

            {

                  SLLNode c = htable[index];

                  while(c.next != null)

                        c=c.next;

                  c.next=newnode;

            }

      }

      public void display()

      {

            for(int i=0;i<tableSize;i++)

            {

                  SLLNode c=htable[i];

                  if(c == null)

                        System.out.println("no elements at index " + i);

                  else

                  {

                        System.out.print("elements at index "+i +" are  ");

                        while(c!=null)

                        {

                              System.out.print(c.data+"->");

                              c=c.next;

                        }

                        System.out.println();

                  }

            }

      }

      public void search(int key)

      {

            int index=key%tableSize;

            if(htable[index]==null)

                  System.out.println("element not found");

            else

            {

                  SLLNode c = htable[index];

                  while(c != null)

                  {

                        if(c.data == key)

                        {

            System.out.println("element found in linked list "+ index);

                              return;

                        }

                        c=c.next;

                  }

                  System.out.println("element not found");

            }

      }

}

public class SeparateChainingDemo

{

      public static void main(String[] args)

      {

            SeparateChaining ob=new SeparateChaining();

            Scanner sc=new Scanner(System.in);

            System.out.println("enter size of the table");

            ob.tableSize=sc.nextInt();

            ob.htable=new SLLNode[ob.tableSize];

            for(int i=0;i<ob.tableSize;i++)

                        ob.htable[i]=null;

            while(true)

            {

      System.out.println("press 1. insert 2. display 3. search 4. exit");

                  int choice=sc.nextInt();

                  switch(choice)

                  {

                  case 1:

                        System.out.println("enter key to be inserted");

                        int key=sc.nextInt();

                        ob.insert(key);

                        break;

                  case 2:

                        ob.display();

                        break;

                  case 3:

                        System.out.println("enter key to be searched");

                        key=sc.nextInt();

                        ob.search(key);

                        break;

                  default:

                        System.exit(0);

                  }

            }

      }

}

Output:
enter size of the table
10
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
1
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
11
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
21
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
31
press 1. insert 2. display 3. search 4. exit
2

no elements at index 0
elements at index 1 are 1->11->21->31->
no elements at index 2
no elements at index 3
no elements at index 4
no elements at index 5
no elements at index 6
no elements at index 7
no elements at index 8
no elements at index 9
press 1. insert 2. display 3. search 4. exit
3
enter key to be searched
1
element found in linked list 1
press 1. insert 2. display 3. search 4. exit
4

Algorithm to insert a value in hash table using separate chaining collision resolution technique

Hashtable is an array of pointers. All pointers are initialized to NULL  

Step1: Read the value to be inserted, key

step 2: create a new node using new operator

step 3: Assign the value read to the data field of newnode (newnode.data =key)

step 4: compute the index

                                        index = key % TABLE_SIZE

step 5: if head[ index] is NULL then

                                        step 5.1:  newnode becomes the only node in linked list or first node

step 6: else

                                        step 6.1 : attach the newnode at the end of linked list as lastnode

Hashing Using Linear Probing : Java Program

Algorithm to insert a value in linear probing

 

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be inserted, x

Step 2:  let i = 0

Step 3 :compute the index at which the x has to be inserted in hash table

                index = (x+ i) % TABLE_SIZE

Step 4: if there is no element at that index then  insert the value at index and STOP

Step 5: If there is already an element at that index

                step 4.1: i = i+1

step 6:  if i < TABLE_SIZE then go to step 3

Algorithm to search a value in linear probing

 

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be searched, x

Step 2:  let i = 0

Step 3: compute the index at which the x can be found
               index = (x+ i) % TABLE_SIZE

Step 4: if the element at that index is same as the search value then print element found and  STOP

Step 5: else

                step 5.1: i = i+1

step 6:  if i < TABLE_SIZE then go to step 3

 

Linear Probing program

import java.util.Scanner;

 

public class LinearProbing

{

      int htable[],tableSize;

      public void insert(int x)

      {

            int i;

            for(i=0;i<tableSize;i++)

            {

                  int index=(x+i)%tableSize;

                  if(htable[index] == -1)

                  {

                        htable[index]=x;

                        break;

                  }

            }

            if(i == tableSize)

                  System.out.println("cannot insert as table is full");

      }

      public void display()

      {

            System.out.println("hash table entries are");

            for(int i=0;i<tableSize;i++)

            {

               System.out.println("element at index "+i+" is " +htable[i]);

            }

      }

      public void search(int x)

      {

            int i;

            for(i=0;i<tableSize;i++)

            {

                  int index=(x+i)%tableSize;

                  if(htable[index] == x)

                  {

                        System.out.println("Search found at index "+index);

                        break;

                  }

            }

            if(i == tableSize)

                  System.out.println("Search element not found");

      }

      public static void main(String[] args)

      {

            LinearProbing ob =new LinearProbing();

            Scanner sc = new Scanner(System.in);

            System.out.println("enter size of the table");

            ob.tableSize=sc.nextInt();

            ob.htable=new int[ob.tableSize];

            for(int i=0;i<ob.tableSize;i++)

                        ob.htable[i]=-1;

            while(true)

            {

              System.out.println("1. insert 2. display 3. search 4. exit");

                  int choice=sc.nextInt();

                  switch(choice)

                  {

                  case 1:

                        System.out.println("enter key to be inserted");

                        x=sc.nextInt();

                        ob.insert(x);

                        break;

                  case 2:

                        ob.display();

                        break;

                  case 3:

                        System.out.println("enter key to be searched");

                        x=sc.nextInt();

                        ob.search(x);

                        break;

                  case 4: return;

                  default:

                       System.out.println("invalid");

                  }

            }

 

      }

 

}

Output:
enter size of the table
10
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
12
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
13
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
14
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
22
press 1. insert 2. display 3. search 4. exit
2
hash table entries are
element at index 0 is -1
element at index 1 is -1
element at index 2 is 12
element at index 3 is 13
element at index 4 is 14
element at index 5 is 22
element at index 6 is -1
element at index 7 is -1
element at index 8 is -1
element at index 9 is -1
press 1. insert 2. display 3. search 4. exit
3
enter key to be searched
22
Search element found at index 5
press 1. insert 2. display 3. search 4. exit

4