Game of Two Stacks Solution

Problem Statement of Game of Two Stacks

You are given two stacks S1 and S2. You have to pic numbers from stack by deleting top element and add them in the resultant sum. The element deleted must be added into the sum. The sum must not exceed the given value of K. Number of elements picked is called score. You have to maximize the score. The original problem statement of Game of Two Stacks challenge is available on Hackerrank.

Basic Greedy Approach for Game of Two Stacks

As the number of elements selected in the resultant set is to be maximized without exceeding K, the Greedy approach can be applied.

Greedy Criteria

Compare the top elements of both stacks and select the smaller one if the total sum does not exceed K. In this way we can select maximum number of elements within the limit of K. Consider the following example, where two stack S1 and S2 are given and K=15.

Game of Two Stacks

Processing of Greedy Approach

Game of Two Stacks

Initially SUM = 0

Game of Two Stacks

SUM = SUM + 2 = 2

Game of Two Stacks

SUM = SUM + 1 = 3

Game of Two Stacks

SUM = SUM + 3 = 6

Game of Two Stacks

SUM = SUM + 1 = 7

Game of Two Stacks

SUM = SUM + 2 = 9

Game of Two Stacks

SUM = SUM + 2 = 11

Game of Two Stacks

SUM = SUM + 3 = 14

Now 5 and 7 are compared and 5 should be selected as it is smaller but by considering 5 the SUM will become 19 which is greater than K (=15). So neither of 5 or 7 can be selected. So We could select 2 elements from stack 1 and 5 elements from stack 2. Our score is 7, which is best.

Pseudo Code for Greedy Solution of Game of Two Stacks

S1 []; // stack 1, n elements stored from 1 to n
S2 []; // stack 2, m elements stored from 1 to m
K;
count = 0; // Too count number of elements selected
SUM = 0;
PSUM = 0
i =  n; // Top of S1
j = m; // Top of S2

While (i > 0 && j >0)
{
	if(S1[ i ] < = S2[ j ]) {
		PSUM = PSUM + S1[ i ];
		i--;
	}
	else {
		PSUM = PSUM + S1[ j ];
		j--;
	}
	if( PSUM <= K) {
		SUM = PSUM;
		count ++;
	}
	else
		break;
}
Print : count;

Analysis of Greedy Approach

The size of stack 1 is n and stack 2 is m. The above approach goes like merge operation for two arrays and hence the time complexity is O(n + m).

O(n) Solution of Game of Two Stacks

The running time can be reduced if reduce the number of comparisons. In above solution we are comparing every element of stack 1 to every element of stack 2. But now we will change the strategy, as follows:

Step 1 – Take Elements from stack 1

First we will take maximum possible elements from stack 1 without the sum exceeding K.

Game of Two Stacks

From stack 1 elements 2,1,5 and 6 are selected.
current_SUM = 2+1+5+6 = 14 (<K)
Best_Score = 4 (4 elements selected)
space_AVAIL = K – current_SUM = 15 – 14 = 1

Step 2 – Include elements from stack 2

Now, we will try to select as many elements as possible from stack 2 in the  space_AVAIL. To try all the possibilities, we will discard elements from stack 1 which are already selected one by one to create room for elements from stack 2 and try to find better solution (maximize Best_Score). space_AVAIL is 1 and 3 is on top of stack 2 so it can not be selected.

Discard Last selected item from stack 1 (‘6’)

Game of Two Stacks

current_SUM = 2+1+5 = 8
space_AVAIL = K – current_SUM = 15 – 8 = 7
current_Score = 3 (as one element is discarded)

Select items from stack 2 (3, 1 and 2) in the space created

Game of Two Stacks

current_SUM = 2+1+5+3+1+2 = 14
space_AVAIL = K – current_SUM = 15 – 14 = 1
current_Score = 6 (3 new elements included)
Best_Score = current_Score = 6 (because current_Score > Best_Score)

Discard next element (‘5’) from stack 1

Game of Two Stacks

current_SUM = 2+1+3+1+2 = 9
space_AVAIL = K – current_SUM = 15 – 9 = 6
current_Score = 5 (1 element excluded)

Select items from stack 2 (2 and 3) in the space created

Game of Two Stacks

current_SUM = 2+1+3+1+2 +2 + 3 = 14
space_AVAIL = K – current_SUM = 15 – 14 = 1
current_Score = 7
(2 new elements included)
Best_Score = current_Score = 7 (because current_Score > Best_Score)

Discard next element (‘1’) from stack 1

Game of Two Stacks

current_SUM = 2+3+1+2 +2 + 3 = 13
space_AVAIL = K – current_SUM = 15 – 13 = 2
current_Score = 6
(1 element excluded)

We can not select any element from stack 2 (7 > space_AVAIL). No improvement in Best_Score.

Discard next element (‘2’) from stack 1

Game of Two Stacks

current_SUM = 3+1+2 +2 + 3 = 11
space_AVAIL = K – current_SUM = 15 – 11 = 4 current_Score = 5
(1 element excluded)

We can not select any element from stack 2 (7 > space_AVAIL). No improvement in Best_Score. Now, no element is there to discard from stack 2. Best score is 7. So the answer is 7.

Pseudo Code for Game of Two Stacks

S1 []; // stack 1, n elements stored from 1 to n
S2 []; // stack 2, m elements stored from 1 to m
K;
current_SUM = 0;
space_AVAIL = k;
current_Score = 0;
Best_Score = 0;
p =  n; // Top of S1
q = m; // Top of S2
while(p > 0 AND (current_SUM + S1[ p ] <= K)) {
	current_SUM = current_SUM + S1[ p ];
	current_Score = current_Score + 1;
	space_AVAIL = K – current_SUM;
	p = p – 1;
}
p = p + 1; \ set on last selected item of stack 1 
Best_Score = current_Score;

While(p <= n) {
	temp_SUM = 0;
	temp_Count = 0;
	while(q > 0 AND space_AVAIL >= 0){
		temp_SUM = temp_SUM + S2[q];
		space_AVAIL = space_AVAIL – S2[q];
temp_Count ++;
		q--;
	}
if(space_AVAIL < 0 ) {
		q = q + 1;
temp_SUM = temp_SUM – S2[q];
space_AVAIL = space_AVAIL + S2[q];
temp_Count -- ;
}
current_SUM = current_SUM + temp_SUM;
Best_Score = current_Score = current_Score + temp_Count;

current_SUM = current_SUM – S1[p];
p++;
space_AVAIL = K – current_SUM;
current_Score = current_Score -1;

temp_SUM = 0;
	temp_Count = 0;
	while(q > 0 AND space_AVAIL >= 0){
		temp_SUM = temp_SUM + S2[q];
		space_AVAIL = space_AVAIL – S2[q];
temp_Count ++;
		q--;
	}
if(space_AVAIL < 0 ) {
		q = q + 1;
temp_SUM = temp_SUM – S2[q];
space_AVAIL = space_AVAIL + S2[q];
temp_Count -- ;
}
current_SUM = current_SUM + temp_SUM;
current_Score = current_Score + temp_Score;
if(current_Score > Best_Score)
	Best_Score = current_Score;
}
Print : Best_Score ; 
Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *