count number of changes two make two strings identical dynamic programming

#include <iostream>
#include <string>
using namespace std;

int min(int x, int y, int z)
{
   return min(min(x, y), z);
}
int editDistance(string str1,string str2,int n,int m )
{
if(n==0)
return m;
if(m==0)
return n;
char a = str1[n-1];
char b = str2[m-1];
    if( a==b )
return editDistance(str1,str2,n-1,m-1);
else
return 1+min(editDistance(str1,str2,n,m-1),editDistance(str1,str2,n-1,m),editDistance(str1,str2,n-1,m-1));
}

int main()
{
 
 string str1 = "pawan";
 string str2 = "rawam";

cout<<editDistance(str1,str2,str1.length(),str2.length());

}

Lowest common Ancestor in tree

#include <iostream>
using namespace std;

struct node
{
int data;
node *left;
node *right;
};

void printTree(node *t){
if(t){
cout<<t->data<<" ";
printTree(t->left);
printTree(t->right);
}
}
node *getNode(int d){

node *temp = new node;
temp->data = d;
temp->left=temp->right = NULL;
return temp;
}
bool isPresent(node *t,int a)
{
if(t!=NULL){
if(t->data==a||isPresent(t->left,a)||isPresent(t->right,a))
return true;
}
return false;
}
node *commonAncestor(node *t,int a,int b)
{
static int count =0;
if(t!=NULL)
{
if((isPresent(t->left,a)&&isPresent(t->right,b))||(isPresent(t->right,a)&&isPresent(t->left,b)))
return t;
node *p= commonAncestor(t->left,a,b);

if(p)
return p;
else
return commonAncestor(t->right,a,b);
}
return NULL;
}
int main (){

node *t = getNode(5);
t->left= getNode(2);
t->right= getNode(7);
t->left->left= getNode(12);
t->right->right= getNode(17);
t->left->right= getNode(21);
t->right->left= getNode(71);
printTree(t);
node *p = commonAncestor(t,71,17);
if(p==NULL)
cout<<"NO common Ancestor";
else
cout<<"common ancestor is "<<p->data;
}

Print sums of all subsets of a given set

#include <iostream>
#include <vector>

using namespace std;

 vector <vector <int> > getSubsets(int set[] ,int n)
{

vector <vector <int> > v;
     int nSub = 1<<n;
     for(int i=0; i<nSub; i++){
      std::vector<int> v1;
          for(int k=0; k<n; k++){
               //if the k-th bit is set
               if( (1<<k) & i){
                    v1.push_back(set[k]);
               }
          }
          v.push_back(v1);
     }
     return v;
}

void sumOfSubsets(vector <vector <int> > v)
{
// cout<<0;
for(int i = 0;i<v.size();i++){
int sum=0;
for(int j = 0;j<v[i].size();j++){
sum +=v[i][j];
}
cout<<sum<<endl;
}
}

int main (){
int set[]= {2,3,4,5};
vector <vector <int> > v =getSubsets(set,sizeof(set)/sizeof(set[0]));

sumOfSubsets(v);
}

Number of flips to make binary string alternate

Given a binary string, that is it contains only 0s and 1s. We need to make this string a sequence of alternate characters by flipping some of the bits, our goal is to minimize the number of bits to be flipped.

Examples

Input : str = “001”
Output : 1
Minimum number of flips required = 1
We can flip 1st bit from 0 to 1 

Input : str = “0001010111”
Output : 2
Minimum number of flips required = 2
We can flip 2nd bit from 0 to 1 and 9th 
bit from 1 to 0 to make alternate 
string “0101010101”.

#include <iostream>
using namespace std;

int numberoftransformsrequired(string a,char expected)
{
int count =0;

for(int i=0;i<a.length();i++){
if(a[i]!=expected)
count++;
if(expected == '1')
expected = '0';
else
expected = '1';
}

return count;
}

int main (){
string a ="1110100001";
cout<<min(numberoftransformsrequired(a,'1'),numberoftransformsrequired(a,'0'));


}

Heapsort in Python

def parent(i):
return i/2

def  left(i):
return 2*i

def  right(i):
return 2*i+1


def heapify(A,i,n):
l=left(i)
r=right(i)
largest=i
if l<=n and A[l]>A[largest]:
largest=l
if r<=n and A[r]>A[largest]:
largest=r
if largest!=i:
A[i],A[largest] =A[largest],A[i]
heapify(A,largest,n)


def length(A):return len(A)-1

def buildheap(A):
n=length(A)
for x in xrange(n/2,-1,-1):
print x
heapify(A,x,length(A))

def heapsort(A):
buildheap(A)
heapsize=length(A)
for i in xrange(heapsize,0,-1) :

A[0],A[i]=A[i],A[0]
heapsize=heapsize-1
heapify(A,0,heapsize)

A=[4,8,1,2,11,3,9]
heapsort(A)
print A

insertion sort in Python

def insertion(A):
x=1
while(x<len(A)):

key=A[x]
i=x-1
while (i>=0)and (A[i]>key):
A[i+1]=A[i]
i=i-1
A[i+1]=key
x+=1
a=[3,2,1,4]
insertion(a)

Check if Expression is Balanced or Not using Stack in Python

import re
balance1 ='2+4-5+[(7+8)-[]]'
balance=list(balance1)
stack=[]
flag=1;

for x in balance:
if re.match('[\(\[\{]',x):
stack.append(x)
else:
if re.match('\)\}\]',x) and stack==[]:
flag=0
break
elif stack!=[]:
if x==')'and stack.pop()!='(':
flag=0
break
if x=='}'and stack.pop()!='{':
flag=0
break
if x==']'and stack.pop()!='[':
flag=0
break
if flag:
print("balanced")
else:
print("Not balanced")