HackerRank Nikita and the Game problem solution

In this HackerRank Nikita and the Game problem solution, we have given an array we need to find and print the maximum number of points we can score.

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)

{"mode":"full","isActive":false}

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;
        }
    }
}

{"mode":"full","isActive":false}

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;
}

{"mode":"full","isActive":false}

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("%d\n", maxSplits(A, 0, N-1));
        free(A);
    } while (--T);

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

{"mode":"full","isActive":false}