Hackerrank - Nikita and the Game Solution

Nikita just came up with a new array game. The rules are as follows:

• Initially, Nikita has an array of integers.
• In each move, Nikita must partition the array into  non-empty contiguous parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets  point; otherwise, the game ends.
• After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array .

Nikita loves this game and wants your help getting the best score possible. Given , can you find and print the maximum number of points she can score?

For example, Nikita starts with the array . She first splits it into  and , then discards . . Discard  leaving . This cannot be further split, so Nikita scored .

Function Description

Complete the arraySplitting function in the editor below. It should return an integer that reperesents the number of times Nikita can split the array.

arraySplitting has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains an integer , the number of test cases.

Each of the next  pairs of lines is as follows:

• The first line contains an integer , the size of array .
• The next line contains  space-separated integers .

Constraints

Scoring

• for  of the test data
• for  of the test data
• for  of the test data

Output Format

For each test case, print Nikita's maximum possible score on a new line.

Sample Input

3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1

Sample Output

0
2
3

Explanation

Test Case 0:

Nikita cannot partition  into  parts having equal sums. Therefore, her maximum possible score is  and we print  on a new line.

Test Case 1:

Initially,  looks like this:

She splits the array into  partitions having equal sums, and then discards the left partition:

She then splits the new array into  partitions having equal sums, and then discards the left partition:

At this point the array only has  element and can no longer be partitioned, so the game ends. Because Nikita successfully split the array twice, she gets  points and we print  on a new line.

Test Case 2:array  a1 a2[4,1,0,1,1,0,1] [4] [1,0,1,1,0,1][1,0,1,1,0,1] [1,0,1] [1,0,1][1,0,1]  [1,0] [1]

The answer is .

Solution in Python

from collections import deque,Counter

def arraySplitting(d,count=0):
	#condition when all the elements in our list have same items
    if len(set(d)) == 1:
        if d[0]==0:
            return len(d)-1
        elif len(d)%2==0:
            l = len(d)
            while not l%2:
                count+=1
                l = l//2
            return count
        else:
            return 0
    a = deque()
    b = deque()
    suma = 0
    sumb = 0
    while d:     
        if suma<sumb or (suma==sumb and not a):
            p = d.popleft()
            suma+=p
            a.append(p)
        else:
            p = d.pop()
            sumb+=p
            b.appendleft(p)
    if not a or not b or suma!=sumb:
        return count
    else:
        count+=1
        return max(arraySplitting(a,count),arraySplitting(b,count))


for _ in range(int(input())):
    n = int(input())
    arr = deque(map(int, input().split()))
    print(arraySplitting(arr))