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'));


}