HackerRank Nikita and the Game problem solution

In this HackerRank Nikita and the Game problem 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 2 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 1 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 arr.

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

HackerRank Nikita and the Game problem solution in Python.

numsets = int(input())

def findMaxMoves(ele, sum):
        sum = sum / 2
        if sum == 0:
            if ele != [0 for x in range(0,len(ele))]:
                return 0
            else:
                return len(ele)-1
        s = 0
        i = 0
        n = len(ele)
        if len(ele) == 1 or len(ele) == 0:
            return 0
        while s != sum and i < n:
            s += ele[i]
            i += 1
        if i >= n:
            return 0
        return 1 + max(findMaxMoves(ele[0:i], sum), findMaxMoves(ele[i:n], sum))
    
def findMaxDeepness(array, amin, amax):
    # print(array, amin, amax)
    if ((amin+amax) % 2 == 0 and (amin+amax) / 2 in array):
            return 1 + max(findMaxDeepness(array,amin,(amin+amax)/2),findMaxDeepness(array,(amin+amax)/2, amax))
    return 0
            
for i in range(numsets):
    els = int(input())
    values = [int(x) for x in input().split(' ')]
    # assert els == len(values)

    print(findMaxMoves(values, sum(values)))
    
    #sumvalues = [sum(values[:i+1]) for i in range(els)]
    #if sumvalues[0] == sumvalues[-1] == 0:
    #    print(els-1)
    #else:
    #    res = findMaxDeepness(sumvalues, 0, sumvalues[-1])
    #    print(res)

Nikita and the Game problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner (System.in);
        int t = scan.nextInt();
        for(int a_0=0;a_0<t;a_0++){
            int n= scan.nextInt();
            int [] arr = new int [n];
            long[]sum = new long [n];
            for(int a_i=0;a_i<n;a_i++){
                arr[a_i]= scan.nextInt();
                if (a_i>0)
                    sum[a_i] = (long)arr[a_i]+sum[a_i-1];
                else 
                    sum[0]= (long)arr[0];
            }
            int score = index(sum,0);
            System.out.println(score);
        }
    }
    static int index(long []arr ,int score) {
        
        int l = arr.length-1;
        if (arr[l]==0){
            score = l;
            return score;
        }
        if (l == 0) return score;
        else if (arr[l]%2 != 0) return score;
        else{
            int pos = Arrays.binarySearch(arr,arr[l]/2);
            //for (int check : arr)
                //System.out.print(check + " ");
            
            //System.out.println("pos "+ pos +" arr[l] "+arr[l] +" arr[l]/2 " + arr[l]/2);
            if (pos < 0){
                //System.out.println("Score!! " + score);
                return score;
            }
            long [] left = new long [pos+1];
            long [] right = new long [l-pos];
            System.arraycopy(arr,0,left,0,pos+1);
            System.arraycopy(arr,pos+1,right,0,l-pos);
            for (int i = 0; i<right.length; i++)
                right[i]-=left[pos];
            int scoreleft = index (left,score+1);
            int scoreright = index(right,score+1);
            score = Math.max(scoreleft,scoreright);
            
            //System.out.println("Problem");
            return score;
        }
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int score(int a[], int begin, int end){
    if (begin+1==end) return 0;
    long long sum = 0;
    for(int i=begin;i<end;i++) sum+=a[i];
    if (sum%2) return 0;
    if (sum==0) return (end-begin-1);
    long long sum2 = 0;
    int where = begin;
    while(sum2<(sum/2)){sum2+=a[where]; where++;}
    if (sum2> (sum/2)) return 0;
    return 1+max(score(a, begin, where), score(a, where, end));
}


int main() {
    int T; cin>>T;
    for(int t=0;t<T;t++){
        int N; cin>>N;
        int a[N];
        for(int i=0;i<N;i++) cin>>a[i];
        cout<<score(a, 0, N)<<endl;
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int max(int a, int b) {
    if (a >= b) return a;
    return b;
}

int maxSplits(int *A, int lo, int hi) {
    int i;
    long sum, sumLo;
    for (i = lo, sum = 0; i <= hi; ++i) {
        sum += A[i];
    }
    if (sum == 0) {
        return (hi-lo);
    }
    for (i = lo, sumLo = 0; sumLo < sum; ++i) {
        sumLo += (long) A[i];
        sum -= (long) A[i];
        if (sumLo == sum) {
            sum = (long) (1 + max(maxSplits(A, lo, i), maxSplits(A, i+1, hi)));
            return (int) sum;
        }
    }
    return 0;
}

int main() {
    static int *A, T, N, i;
    scanf("%d", &T);
    do {
        scanf("%d", &N);
        A = malloc(N * sizeof(int));
        for (i = 0; i < N; ++i) {
            scanf("%d", &A[i]);
        }
        printf("%dn", maxSplits(A, 0, N-1));
        free(A);
    } while (--T);

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}