Sunday, March 17, 2013

Gambling game

In a game, you bet using the following strategy. Whenever you lose a bet, you double the value of the bet for the next round. Whenever you win, the bet for the next round will be one dollar. You start the round by betting one dollar.

For example, if you start with 20 dollars, and you win the bet in the first round, lose the bet in the next two rounds and then win the bet in the fourth round, you will end up with 20+1-1-2+4 = 22 dollars.

You are expected to complete the function, getFinalAmount, which takes two arguments. The first argument is an integer initialAmount which is the initial money we amount we have when we start the betting. The second argument is a string betResultsThe ith character of outcome will be either 'W' (win) or 'L' (lose), denoting the result of the ith round.
Your function should return the amount of money you will have after all the rounds are played. If at some point you don't have enough money in your account to cover the value of the bet, you must stop and return the sum you have at that point.

Sample Test Cases:

Input #00:
12
WWWWWWWW

Output #00:
20

Explanation:
The initial amount is 12, for every win, you gain 1 dollar.
There are totally 8 consecutive wins and no losses, hence total money gained = 12 + 8 = 20

Input #01:
15
LLLWLLLL

Output #01:
1

Explanation:
The initial amount is 15. As stated in the problem, the amount of bet doubles for every loss.
1st round - Loss: 15-1 = 14
2nd round - Loss: 14-2 = 12 (Bet doubles)
3rd round - Loss: 12-4 = 8
4th round - Win: 8 + 8 = 16
5th round - Loss:16-1 = 15 (Since the previous bet was a win, this bet has a value of 1 dollar)
6th round - Loss: 15-2 = 13
7th round - Loss: 13-4 = 9
8th round - Loss: 9-8 = 1

#include<iostream>
#include<string.h>
using namespace std;
int getFinalAmount(int init,char result[100])
{
int amt=1;
for(int i=0;i<strlen(result);i++)
{
if(result[i]=='W' || result[i]=='w')
{
if(init < amt)
{
return init;
}
init+=amt;
amt=1;
}
else if(result[i]=='L' || result[i]=='l')
{
if(init < amt)
{
return init;
}
init-=amt;
amt*=2;
}
}
return init;
}
int main()
{
int T;
int win,lose,init;
char result[100];
cin>>T;
while(T--)
{
cin>>init;
cin>>result;
cout<<getFinalAmount(init,result)<<endl;
}
}
Input:
2
12
WWWWWWWW
15
LLLWLLLL

Output:
20
1

Thursday, February 14, 2013

Number-to-Alphabet Decoding System


Problem
There is a coding system where all the letters in an Alphabet is coded into a number such as a-->1, b-->2,..., z-->26. Given an array of the integers, the program should output the number of possible letter arrangements in the decoded string.
C++ Program
#include<iostream>
using namespace std;
#define SIZE 4
int getCount(int A[SIZE],int s)
{
if(s>=SIZE - 1)
{
return 1;
}
else
{
if(A[s]*10 + A[s+1] <= 26)
{
return getCount(A,s+1) + getCount(A,s+2);
}
else if(A[s] <= 26)
{
return getCount(A,s+1);
}
else
{
return 0;
}
}
}
int main()
{
//int A[SIZE]={1,2,6,1,2,4};
int A[SIZE]={1,1,2,3};
int s=0;
cout<<"Recursive: "<<getCount(A,s)<<endl;
int a=1;
int b=1;
int ans=a;
int n=SIZE;
if(10*A[n-2]+A[n-1] <= 26)
{
a=2;
}
for(int i=n-3; i>=0; i--)
{
if(10*A[i]+A[i+1] <= 26)
{
ans=a+b;
b=a;
a=ans;
}
else
{
ans=a;
b=a;
}
}
cout<<"Dynamic Programming: "<<ans<<endl;
}
Output
Recursive: 5
Dynamic Programming: 5

Process returned 0 (0x0) execution time : 0.018 s
Press any key to continue.

Thursday, January 17, 2013

C++ program for jumps problem

Given an array of positive numbers, find the number of ways to reach the end of the array in minimum number of steps where the value at each index represents the maximum number of steps one can move.
Sample Input:
The first line contains a number n, the number of elements in the array. The second line contains n space separated numbers.
11
1 3 5 8 9 2 6 7 6 8 9
Sample Output
Output should contain n space separated numbers, each represents the number of ways at that index.
2 2 4 1 1 2 1 1 1 1 0
#include<iostream>
using namespace std;
int main()
{
int n,A[100];
cin>>n;
int max=-9999999;
for(int i=0;i<n;i++)
{
cin>>A[i];
if(A[i]>max)
{
max=A[i];
}
}
//cout<<max<<endl;
cout<<"The given array is:\n";
for(int i=0;i<n;i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
int B[100]={0};
for(int i=0;i<n-1;i++)
{
B[i]=A[i];
}
for(int i=n-2;i>=0;i--)
{
if(i+A[i] >= n-1)
{
B[i]=1;
}
else
{
int min=max;
bool inside = false;
for(int j=i+A[i];j>i;j--)
{
if(B[j]!=0 && B[j]<=min)
{
min=B[j];
inside = true;
}
}
if(inside)
{
B[i]=min+1;
}
}
}
cout<<"The distance array is:\n";
for(int i=0;i<n;i++)
{
cout<<B[i]<<" ";
}
cout<<endl;
int num[100]={0};
for(int i=n-2;i>=0;i--)
{
if(B[i]==1)
{
num[i]=B[i];
}
else
{
for(int j=1;i+j<n && j<=A[i];j++)
{
if(B[i+j]==B[i]-1)
{
//cout<<i<<" "<<B[i]<<" "<<j<<endl;
num[i]+=num[i+j];
}
}
}
}
cout<<"Number of ways:\n";
for(int i=0;i<n;i++)
{
cout<<num[i]<<" ";
}
cout<<endl;
}
11
1 3 5 8 9 2 6 7 6 8 9
The given array is:
1 3 5 8 9 2 6 7 6 8 9
The distance array is:
3 2 2 1 1 2 1 1 1 1 0
Number of ways:
2 2 4 1 1 2 1 1 1 1 0

Saturday, January 12, 2013

C++ program to find all the possible interleavings of two input strings


#include<iostream>
#include<string.h>
#include<map>
using namespace std;
map<string,bool> myMap;
void generateInterleaved(char A[100],char B[100],char out[200],int start1,int start2)
{
if(strlen(out)==strlen(A)+strlen(B))
{
if(myMap.find(out) == myMap.end())
{
myMap[out]=true;
}
return;
}
else
{
if(start1<strlen(A))
{
out[strlen(out)]=A[start1];
generateInterleaved(A,B,out,start1+1,start2);
out[strlen(out)-1]=0;
}
if(start2<strlen(B))
{
out[strlen(out)]=B[start2];
generateInterleaved(A,B,out,start1,start2+1);
out[strlen(out)-1]=0;
}
}
}
int main()
{
char A[100],B[100],C[100];
bool isInterleaved(char[],char[],char[]);
cin>>A>>B>>C;
bool result=isInterleaved(A,B,C);
if(result==true)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
char out[200]={0};
cout<<"The possible interleavings are:\n";
generateInterleaved(A,B,out,0,0);
for(map<string,bool>::iterator it = myMap.begin();it != myMap.end(); ++it)
{
cout<<it->first<<endl;
}
}
bool isInterleaved(char A[100],char B[100],char C[100])
{
int j=0,k=0;
for(int i=0;i<strlen(C);i++)
{
if(j<strlen(A) && C[i]==A[j])
{
j++;
}
else if(k<strlen(B) && C[i]==B[k])
{
k++;
}
}
if(j==strlen(A) && k==strlen(B))
{
return true;
}
else
{
return false;
}
}
Input:
ab
cd
Output:
ab
cd
abcd
YES
The possible interleavings are:
abcd
acbd
acdb
cabd
cadb
cdab

Tuesday, December 4, 2012

Find the Largest Sum Path from root to leaf in a binary tree


#include<iostream>
#define SMALL -999999
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
new_node->parent=NULL;
return new_node;
}
void parentfinder(node *root,node *parent)
{
if(root)
{
root->parent=parent;
parent=root;
parentfinder(root->left,parent);
parentfinder(root->right,parent);
}
return;
}
int height(struct node* root)
{
if(root==NULL)
{
return 0;
}
else
{
int lheight=1+height(root->left);
int rheight=1+height(root->right);
return lheight>rheight?lheight:rheight;
}
}
void levelorderprint(struct node* root,int level)
{
if(root && level==0)
{
cout<<root->data<<"->";
if(root->parent)
{
cout<<root->parent->data<<endl;
}
}
else if(root)
{
levelorderprint(root->left,level-1);
levelorderprint(root->right,level-1);
}
}
void levelorder(struct node* root)
{
int h=height(root);
for(int i=0;i<h;i++)
{
levelorderprint(root,i);
cout<<endl;
}
}
struct node** summer(node *root,node **maximum,node *parent)
{
if(root)
{
if(parent)
{
root->data=root->data+parent->data;
if((*maximum)->data<root->data)
{
*maximum=root;
}
}
parent=root;
summer(root->left,maximum,parent);
summer(root->right,maximum,parent);
}
return maximum;
}
int searchformax(node *root,node **max,bool *found,int A[100])
{
static int i=0;
if(root)
{
if(root==*max)
{
*found=true;
}
if(!(*found))
{
searchformax(root->left,max,found,A);
if(!(*found))
{
searchformax(root->right,max,found,A);
}
}
if(*found)
{
A[i]=root->data;
i++;
}
}
return i;
}
int main()
{
struct node* root=createnode(1);
root->left=createnode(2);
root->right=createnode(3);
root->left->right=createnode(4);
root->left->left=createnode(5);
root->right->right=createnode(-6);
root->right->left=createnode(7);
root->right->right->left=createnode(8);
//root->right->right->left->left=createnode(10);
root->right->right->right=createnode(10);
parentfinder(root,NULL);
levelorder(root);
node *ptr=new struct node;
ptr->data=SMALL;
node **max=&ptr;
max = summer(root,max,NULL);
bool var=false;
bool *found = &var;
int A[100];
int count=searchformax(root,max,found,A);
for(int i=0;i<count-1;i++)
{
A[i]=A[i]-A[i+1];
}
cout<<"The path is:"<<endl;
while(count--)
{
cout<<A[count]<<endl;
}
}
Output:
1->
2->1
3->1

5->2
4->2
7->3
-6->3

8->-6
10->-6

The maximum sum path is:
1
3
7

Tuesday, November 27, 2012

Given two nodes of a Binary Tree, write a program to determine the shortest distance between the two nodes.

Approach:
1. Find the lowest common ancestor of the given nodes.
2. Find the distance (levels) between the lowest common ancestor and each given node separately.
3. Add the distances obtained in Step-2.

#include<iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
if(root)
{
if(root==n1)
{
return 1;
}
else if(root==n2)
{
return 1;
}
else
{
return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
}
}
else
{
return 0;
}
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
if(root)
{
int lf = help_anc(root->left,n1,n2);
int rf = help_anc(root->right,n1,n2);
if(lf==1 && rf==1)
{
return root;
}
else
{
node* lca = Ancestor(root->left,n1,n2);
if(lca!=NULL)
{
return lca;
}
lca = Ancestor(root->right,n1,n2);
return lca;
}
}
else
{
return NULL;
}
}

int customheight(node *root,node *n1,bool *found)
{
int lheight=0,rheight=0;
if(root)
{
if(*found==false && root==n1)
{
*found=true;
return 0;
}
else if(*found==false)
{
lheight=customheight(root->left,n1,found);
rheight=0;
if(*found==false)
{
rheight=customheight(root->right,n1,found);
}
if(*found==true)
{
return lheight>rheight?1+lheight:1+rheight;
}
else
{
return 0;
}
}
else
{
return 0;
}
}
else
{
return 0;
}
}
int distancethroughlca(node* n1,node* n2,node* lca)
{
if(lca)
{
bool found=false;
int dist1=customheight(lca,n1,&found);
cout<<"Distance of "<<n1->data<<": "<<dist1<<endl;
found=false;
int dist2=customheight(lca,n2,&found);
cout<<"Distance of "<<n2->data<<": "<<dist2<<endl;
return dist1+dist2;
}
else
{
return 0;
}
}

int main()
{
struct node* root=createnode(1);
root->left=createnode(2);
root->right=createnode(3);
root->left->right=createnode(4);
root->left->left=createnode(5);
root->right->right=createnode(6);
root->right->left=createnode(7);
root->right->right->left=createnode(8);
//root->right->right->left->left=createnode(10);
root->right->right->right=createnode(10);
struct node* n1 = root->right->right->left;
struct node* n2 = root->right->right->right;
struct node* lca=Ancestor(root,n1,n2);
if(lca)
{
cout<<"Least Common Ancestor: "<<lca->data<<endl;
}
cout<<"Total distance through LCA: "<<distancethroughlca(n1,n2,lca)<<endl;
}
Output:
Least Common Ancestor: 1
Distance of 8: 3
Distance of 4: 2
Total distance through LCA: 5

Saturday, November 24, 2012

C++ program for Heapsort

#include<iostream>
#define SIZE 9
using namespace std;
void Maxheapify(int A[SIZE],int i,int heapsize)
{
int largest=i;
if(2*i <heapsize && A[i]<A[2*i])
{
largest=2*i;
}
if(2*i+1 <heapsize && A[largest]<A[2*i+1])
{
largest=2*i+1;
}
if(largest!=i)
{
int t=A[i];
A[i]=A[largest];
A[largest]=t;
Maxheapify(A,largest,heapsize);
}
}
void Buildmaxheap(int A[SIZE],int heapsize)
{
int size=heapsize;
for(int i=size/2;i>=0;i--)
{
Maxheapify(A,i,heapsize);
}
}
void Heapsort(int A[SIZE])
{
Buildmaxheap(A,SIZE);
cout<<endl;
int heapsize=SIZE;
for(int i=SIZE-1;i>=1;i--)
{
int t=A[0];
A[0]=A[i];
A[i]=t;
heapsize--;
Maxheapify(A,0,heapsize);
}
}
int main()
{
int A[SIZE]={9,2,1,8,7,2,4,3,5};
cout<<"The given array:\n";
for(int i=0;i<SIZE;i++)
{
cout<<A[i]<<" ";
}
Heapsort(A);
cout<<"The sorted array:\n";
for(int i=0;i<SIZE;i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
}