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)
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
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) #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 <= x: #print(b) replacement_list_sum = replacement_list_sum + b 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
I changed my code and still taking ages