Maximum ways for a boolean expression to evaluate to true.

Solution: Lets say that T(p,q) represents the number of ways operands between p and q evaluate to true and F(p,q) represents the number of ways operands between p and q evaluate to false.

then T(p,q) =

ways for all i between p and q

    if expr[i] is &,   T(p,i-1) * T(i+1,q)

    if expr[i] is |,   T(p,i-1) * T(i+1,q)  +   F(p,i-1) * T(i+1,q) + 
                       T(p,i-1) * F(i+1,q)

    if expr[i] is ^,   F(p,i-1) * T(i+1,q)  +   T(p,i-1) * F(i+1,q)

and F(p,q) =

ways for all i between p and q

    if expr[i] is &,   F(p,i-1) * F(i+1,q)  +  F(p,i-1) * T(i+1,q)  + 
                       T(p,i-1) * F(i+1,q)

    if expr[i] is |,   F(p,i-1) * F(i+1,q) 

    if expr[i] is ^,   F(p,i-1) * F(i+1,q) + T(p,i-1) * T(i+1,q)

 

// the below code is written in C++

#include<bits/stdc++.h>
using namespace std;

// t[i][j] and f[i][j] represents total number of ways the subexpression (expr from i t0 // j) can be evaluated to true and false resp.
int t[100][100],f[100][100];

int falseWays(string s,int p,int q);
int trueWays(string s,int p,int q)
{
if(p>q)
return 0;

if(p==q) return s[p]=='T';

if(t[p][q]!=-1)
return t[p][q];

int ways=0;
int i;

for(i=p;i<=q;i++)
{
if(s[i]=='|')
{
ways+=trueWays(s,p,i-1)*trueWays(s,i+1,q) +
      trueWays(s,p,i-1)*falseWays(s,i+1,q) +
      falseWays(s,p,i-1)*trueWays(s,i+1,q);
}

if(s[i]=='&')
{
ways+=trueWays(s,p,i-1)*trueWays(s,i+1,q);
}

if(s[i]=='^')
{
ways+=trueWays(s,p,i-1)*falseWays(s,i+1,q)+
      falseWays(s,p,i-1)*trueWays(s,i+1,q);
}
}

t[p][q]=ways;
return ways;
}

int falseWays(string s,int p,int q)
{
if(p>q)
return 0;

if(p==q) return s[p]=='F';

if(f[p][q]!=-1)
return f[p][q];

int ways=0;
int i;

for(i=p;i<=q;i++)
{
if(s[i]=='|')
{
ways+=falseWays(s,p,i-1)*falseWays(s,i+1,q);
}

if(s[i]=='&')
{
ways+=falseWays(s,p,i-1)*falseWays(s,i+1,q) +
      trueWays(s,p,i-1)*falseWays(s,i+1,q) +
      falseWays(s,p,i-1)*trueWays(s,i+1,q);
}

if(s[i]=='^')
{
ways+=falseWays(s,p,i-1)*falseWays(s,i+1,q) +
      trueWays(s,p,i-1)*trueWays(s,i+1,q);
}
}

f[p][q]=ways;
return ways;
}

int main()
{
string s="T|F&T|T";   // given string.
int i,j;

int l=s.length();     // l is length of given string.

// setting all elements of t and f as -1.
for(i=0;i<=l;i++)
for(j=0;j<=l;j++)
{
t[i][j]=-1;
f[i][j]=-1;
}

cout<<trueWays(s,0,l-1)<<endl;

return 0;
}

 

Number of ways N dices can make sum S

Problem: Given N dices. Each dice has A faces.
Find the total number of ways these dices can make sum S when all are thrown together.
// the below code is written in C++.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int s=10;  // This is the required Sum we want to generate
int n=5;   // n is total number of dices.
int A=6;
// A is number of faces each dice has. Each face has one unique number from 1 to A.
int i,j,k;

// d[i][j] depicts number of ways i dices can make sum of j.
long long int d[n+1][s+1];

// setting no. of ways for one dice to make sum 1 to A as 1.
for(i=1;i<=A;i++)
{
d[1][i]=1;
}

// after A, no. of ways is 0.
for(i=A+1;i<=s;i++)
{
d[1][i]=0;
}

// setting no. of ways for all dices to make sum 0 as 0.
for(i=1;i<=n;i++)
d[i][0]=0;

for(i=2;i<=n;i++)    // for i no. of dices.
{
   for(j=1;j<=s;j++) //  for sum j.
   {
        long long int cnt=0;
        for(k=1;k<=A;k++)     // for each face.
        {
            if(j-k>=0)
            {
//  taking k for i-th dice and taking rest j-k for other (i-1) dices.
               cnt+=d[i-1][j-k];      
            }
        }
        d[i][j]=cnt;
   }
}
cout<<"no. of ways : "<<d[n][s]<<endl;

return 0;
}

Complexities :

Time complexity:    O(N*S*A)

Space complexity:   O(N*S)

Merging two sorted Link lists without making new node.

    
/*
  Merge two sorted lists A and B as one linked list.
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/



Node* MergeLists(Node *headA, Node* headB)
{
    // This method will take two parameters as pointer to head nodes of both link list,
    // and return pointer to head node of merged sorted link list.
    
    Node *prevA,*prevB,*temp;
    prevA=NULL;
    
    // Plan to merge B in A. So, set returning pointer point to the head of A.
    Node * ans=headA;   
    while(headA && headB)
        {
        
        
        // if current node value of A is greater or equal to that of B.
        if(headA->data >= headB->data)
            {
              
                
                // if prevA is not NULL.
                if(prevA)
                   {
                   temp=headB;
                   headB=headB->next;
                   temp->next=headA;
                   prevA->next=temp;
                   prevA=temp;
                }
                
                
                // if prevA is NULL.
                else 
                   {
                     
                    temp=headB;
                    headB=headB->next;
                    temp->next=headA;
                    prevA=temp;
                    ans=temp;
               }
               
        }
        
        
        // if current node value of A is less than that of B.
        else if(headA->data < headB->data)
            {
                       
            prevA=headA;
            headA=headA->next;   
        }
       
        
    }
      
     if(!headA && headB)
        {
         
         // if A is exhausted but B is not. So, link last node of A to head of B.
         if(prevA)
           prevA->next=headB;
         
         
         // if Given A is NULL. So, make returning node point to the head of B.   
         else 
           ans=headB;
         
         }
     
    return ans;
    
}


Time Complexity : O(m+n)
m=length of link list A.
n=length of link list B.
Space Complexity : O(1)