Hackerrank - Nikita and the Game Solution
3 min read

Hackerrank - Nikita and the Game Solution

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))

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×