Its just an example of multiplying any number by 2^n-1 or 2^n+1 without using any multiplication symbol.

//multiplication of the number by 2^n+1 2^n-1

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>//will not work in linux

main()

{

      int n=3;

      int m=n<<3;

      printf("%d\n",(m-n));//multiplying 3 by 7

      printf("%d",(m+n));//multiplying 3 by 9

      getch();

      }

Find highest length substring such that there are equal number of 0’s and 1’sin array of 1’s and 0’s only

I saw this question on some site stating it was asked in some campus placement....so here is the solution..

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

  main()
{
    char ch[100];
    int l;
    int num0=0;
    int num1=0;
    int even=0;

    puts("Enetr the string\n");
    gets(ch);//need not to put & since ch is itself a pointer
    l=strlen(ch);
    int t=l;
    if(l%2==0)
    even=1;
    printf("%d\n",l);
    for(int i=0;i<l;i++)
    {
            if(ch[i]=='0')
            num0++;
            else
            num1++;
            }
            if((num0==num1))
            {
                                 puts("Length of max substring having equal number of zeros and one\n");
                                 printf("%d",l);
                                 }
                                 else{
                                      if(even==0)
                                      t=t+1;
                                      int i=0;
                                      num0=0;
                                      num1=0;
                                      int j=0;
                                 while(t!=0)
                                 {          int w=0;
                                            t=t-2;
                                            j=t;
                                            while(j!=(l+1))
                                            {
                                            for( i=w;i<j;i++)
                                            {
                                                 if(ch[i]=='0')
                                                 num0++;
                                                 else
                                                 num1++;
                                                 
                                                    }
                                                    if(num0==num1)
                                                    {
                                                                  printf("Maximum substring having equal number of 0's and 1's is %d between %d",w,j-1);
                                                                  getch();
                                                                  }
                                                    else{
                                                         num0=0;
                                                         num1=0;          
                                                    w=w+1;
                                                    j=j+1;
                                                    }
                                                    }
                                         
                                            }
                                            }
         
    getch();
 }

Traversing link-list in Reverse Order(Recursion)

Here we traversing the singly-link list in reverse order without saving the contents in another strucutre


#include<stdio.h>
#include<conio.h>
#include<malloc.h>


struct link
{
    int data;
  struct link *next;
 
    };
   
    void add(struct link **p,int d)
    {struct link *r,*q;
    q=*p;
    if(*p==NULL)
    {
    r=(struct link *)malloc(sizeof(struct link));
    r->data=d;
    r->next=NULL;
    *p=r;
   
    }
    else
    {
    while(q->next!=NULL)
    {q=q->next;
  }
     r=(struct link *)malloc(sizeof(struct link));
      r->data=d;
    r->next=NULL;
    q->next=r;
   
  }
   
  }
  void display(struct link **p)
  {
  struct link *q=*p;
  while(q!=NULL)
  {
  printf("%d\n",q->data);
q=q->next;
 }
  }
  void reversetraverse(struct link *p)//using recursion we traversing 
  {
struct link *q=p;
if(q->next==NULL)
{
     printf("%d\n",q->data);
return;
}
reversetraverse(q->next);
printf("%d\n",q->data);
 
 
}
 
   
   
    main()
    {
  struct link *p;
  p=NULL;
 
  add(&p,5);
add(&p,5);
 add(&p,6);
display(&p);
reversetraverse(p);
  getch();
  }

Recursion-Reversing a String(JAVA)

public class Reverse
{
String s;
static String r="";
 
 public Reverse()
{
}
public void reverse(String s,int i)//earlier we tried using only string as an argument in that case i would be either static or class variable and in both case for all the stack elements value if i would be 5 hence output will "yyyyy"
{

if(i==5)
{
r=r+s.charAt(i);
return;

}
reverse(s,i+1);
r=r+s.charAt(i);//everything that comes after the function call is call in the reverse method we have used that concept
}
public static void main (String args[])
{
Reverse obj=new Reverse();
obj.reverse("Tanmay",0);
System.out.println(obj.r);
}
}

Static Stacks

Static Implementation of Stack  through C

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define max 10
struct stack
{
    int a[max];
    int top;
    };
   
void push(struct stack *p,int n)
{
  if(p->top==max-1)
 
 {
printf("STACK FULL");
 }
  else
  {
  p->a[++p->top]=n;
}
 
 }//end of push

 int pop(struct stack *p)
 {
  if(p->top==-1)
  {
printf("\nStack is empty\n");
return -999;
           }
else
return p->a[p->top--];
 }//end of POP

int peek(struct stack *p)
{
  if(p->top!=max-1)
  return p->a[p->top];
}//help us to see the top most element of the stack without removing it


 int menu(struct stack *s)
 {
  printf("\n1.PUSH\n2.POP\n3.PEEK\n4.EXIT\n");
 int a;
 do
 {
 printf("Enetr the choice\n");
 scanf("%d",&a);

      switch(a)
      {
 case 1:
 
   printf("Enter the number\n");
   int n;
  scanf("%d",&n);
   push(s,n);
   return 1;
    break;
  case 2:
  printf("%d\n",pop(s));
  return 2;
  break;
  case 3:printf("%d",peek(s));
  return 3;
  case 4:return 4;
  break;
}

      }while(a>4||a<1);
 
  }
 

 main()
 {
    struct stack s;
    s.top=-1;
    int x;
  do{
  x=menu(&s);
}while(x!=4);
 
    getch();
    }
 

QUICK SORT

Quick sort is divide and conquer algorithm .Its one of the most influential algorithm of 20th century.

Its a top down approach every time a element  is taken and is fixed to some position and then from that fixed place array is portioned in two sub arrays(fixing the position of the pivot is termed as portioning the data) which a recursively portioned further.
It is in place sorting algorithm or in situ

Generally we make first element as the pivot in an array but this in all ready  sorted array does n^2 number of steps thus we prefer to do random shuffling to an array before passing it to quick sort function

Explanation-Here we have taken first element of  the array as the pivot we can take any element as the pivot or median for the best performance.If an array was sorted then we would have taken first element as pivot it would have resulted in worst performance.Thus while doing qsort we must put the given array to a shuffling function

Here split function helps in implementing the divide and conquer stuff by dividing the array into sub-arrays and qsort fixes the position of pivot

Time complexity

Best Case  nlogn (in best case number of compares are 1.39nlog(n))

Average Case   nlogn  (Depth of recursion is logarthmic)  

Worst Case n^2

Space Complexity O(n)

Stability* -In normal and efficient implementation of Quick sorting it is not  stable

Shuffling is needed for performance grantee

Optimizing  quick sort

• Use of extra array may help in partitioning but its not worth using it because it takes extra memory(and becomes same as merge sorting)
• it can be improved by using cut off ie after dividing array into small sub arrays and applying insertion sort, insertion sort handles the nearly sorted array efficiently and moreover it can sort the numbers during runtime
•  we can make pivot=median of the data and for large data we can get the median by taking sample the data

Comparison

In average case merge sorting do 39% more compares than quick sorting but quick sorting is faster than merge sorting because it has less data movement

Insertion and merge sort are stable while bubble selection and quick(in an efficient implimentation) are not stable

Insertion and merge sort are stable because in their algorithm we never make equal item pass or swap

What are stable sorting algorithms-:

In a stable sorting algorithms  relative order of the equal elements are maintained because we never swap the elements having the equal values(use full when we have lot many fields and need to arrange the data according to any field as required)

power of 2 in constant time

Checking if number can be presented in power of 2 in constant time:

Algorithm

Number which can be represented in power of 2 its binary form will have 1 only at msb while
number one less than it will have 0 at msb while all other will have 1.
For examble
64=1000000
63=0111111
Now if we multiply each bit of 64 with corresponding bit of 63 we will get 0

SOURCECODE
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int m=64;
int n=63;
if((m&n)==0)//bitwise operator
cout<<"yes number can be represented in power of two";
else
cout<<"cannot be represented in power of two";
getch();
}