CODEWITHSUNDEEP
python
Sumit
Sumit

Reputation: 2023

Game of two stacks (hackers rank problem) algorithm

I was solving problem for game of two stacks on Hackers rank and got stuck. Problem is my solution is not working when stack count is very huge (millions of entries)

https://www.hackerrank.com/challenges/game-of-two-stacks

Alexa has two stacks of non-negative integers, stack A and stack B where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game:

In each move, Nick can remove one integer from the top of either stack A or B stack.

Nick keeps a running sum of the integers he removes from the two stacks.

Nick is disqualified from the game if, at any point, his running sum becomes greater than some integer X given at the beginning of the game.

Nick's final score is the total number of integers he has removed from the two stacks.

find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified) during each game and print it on a new line.

For each of the games, print an integer on a new line denoting the maximum possible score Nick can achieve without being disqualified.

Sample Input 0

1 -> Number of games
10 -> sum should not exceed 10 
4 2 4 6 1  -> Stack A
2 1 8 5 -> Stack B

Sample Output 

4

Below is my solution

def twoStacks(x, a, b):
a_list = []
sum_list = 0
for i in range(len(a)):
    sum_list = sum_list + a[i]
    if sum_list <= x:
        a_list.append(a[i])
    else:
        break

print(a_list)

print(a[i])
print(sum_list)
max_first = len(a_list)
replacement_list = []

list_a_length = len(a_list)
list_replacement_length = len(replacement_list)
list_b_length = len(b)
replacement_list_sum = 0
a_list_sum = sum(a_list)
while True:
    max_first = max(max_first, list_a_length + list_replacement_length)

    #print("max final is ",max_first)
    #print(sum(replacement_list))
    #print(sum(a_list))
    #print(b[0])
    #print(type(replacement_list), type(a_list), type(b))
    #print("sum of a lis is", sum(a_list))
    if list_b_length == 0:
        break
    elif replacement_list_sum + a_list_sum + b[0] <= x:
        #print(b[0])
        replacement_list_sum = replacement_list_sum + b[0]
        replacement_list.append(b.pop(0))
        list_replacement_length += 1
        list_b_length -= 1
        if replacement_list_sum  > x:
            break
    elif a_list:
        a_list_sum = a_list_sum - a_list[-1]
        a_list.pop()
        list_a_length -= 1
        #print(a_list)
    else:
        break
# print(replacement_list)
# print(a_list)
return max_first

Where a is the first stack , b is second stack and x is sum in range of (1000000000)

Problem is my code is giving correct results but for large number it takes ages to give the output. any better solution is appreciated

Edit:

I changed my code and still taking ages

Upvotes: 0

Views: 978

Answers (2)

Christian Sloper
Christian Sloper

Reputation: 7510

Initial observations:
a) The order Nick picks the solution does not matter.If S = { a1, b1,a2,b2,... } you can reorder this and pick everyone from A first, then pick B.

b) If you have a solution S = S_A + S_B , consisting of S_A elements of A and S_B elements of B. You can rephrase the solution as "Some elements S_A of A" + " as many elements as possible from B given S_A ".

Suggested pseudo code:
1) Iterate through stack A. Keep the cumulative sum.
2) For each step through A, check how many elements you can pick from B.

Optimization if necessary: You can create all cumulative sums from B, and for each partial solution from A do a binary search on this sum table to quickly determine how many elements you can grab from B.

Here is an implementaion of the suggested idea, it solves the hackerrank problem, so its kinda cheating for you if you use it :-) :

from itertools import accumulate
import bisect

def twoStacks(x,a,b):
    cum_sum_b = list(accumulate(b))
    cum_sum_a = [0]+list(accumulate(a))
    return max( bisect.bisect_right(cum_sum_b, x-a_sum ) +i for i, a_sum in enumerate(cum_sum_a) if a_sum <= x)

Upvotes: 3

Krishna
Krishna

Reputation: 481

I could see that you are not exiting the initial for loop once you met the criteria. You are going through the entire list even after the criteria is met, which can be avoided. Try to break out of the loop once the criteria is met.

 for i in range(len(a)):
        sum_list = sum_list + a[i]
        if sum_list <= x:
            a_list.append(a[i])
        else:
            break

This would definitely improve the performance in case of a large number of values for list a.

Upvotes: 2

Related Questions