HackerRank Nikita and the Game Problem Solution

In this post, we will solve 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?
For example, Nikita starts with the array arr = [1, 2, 3, 6]. She first splits it into
a1 = [1, 2, 3] and a2 = [6], then discards a2. arr = al → al = [1, 2], a2 = [3].
Discard a2 leaving arr = [1,2]. This cannot be further split, so Nikita scored 2.

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 t, the number of test cases.
Each of the next t pairs of lines is as follows:

The first line contains an integer n. the size of array arr.
The next line contains n space-separated integers arr[i].

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

HackerRank Nikita and the Game Problem Solution

Nikita and the Game C Solution

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

long long sum[16384];

int getPoint(int low, int high, long long target) {
    int point, tmp, start, end, mid;
    
    start = low;
    end = high;
    point = 0;
    while (start <= end) {
        mid = (start+end)/2;
        if (sum[high]-sum[mid] < target) {
            end = mid - 1;
        } else if (sum[high]-sum[mid] > target) {
            start = mid + 1;
        } else {
            if (target%2 == 0) {
                point = getPoint(low, mid, target/2);
                tmp = getPoint(mid+1, high, target/2);
                if (tmp > point) {
                    point = tmp;
                }
            }
            point += 1;
            break;
        }
    }
    return point;
}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int t, n, i, j, num;
       
    scanf("%d", &t);
    for (i=0; i<t; i++) {
        scanf("%d", &n);
        scanf("%d", &num);
        sum[0] = num;
        for (j=1; j<n; j++) {
            scanf("%d", &num);
            sum[j] = sum[j-1] + num;
        }
        if (sum[n-1] == 0) {
            printf("%d\n", n-1);
        } else {
            if (sum[n-1]%2 == 0) {
                printf("%d\n", getPoint(0, n-1, sum[n-1]/2));
            } else {
                printf("0\n");
            }
        }
    }
    
    return 0;
}

Nikita and the Game C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,arr[999999], d=0;
ll suml=0,sumr=0;
    
ll desti(ll st,ll en)
    {//cout<<"st: "<<st <<"en :"<<en<<endl;
    //ll i=st,j=en;
    if(st>n || st<0 || en>n || en<0)
        return 0;
    else{
    stack<ll> s,s1;
     suml=0,sumr=0;
    for(ll i=st;i<en;i++)
        {
        s.push(arr[i]);
        suml+=s.top();    
    }//return suml;
    if(suml==0)
        return s.size()-1;
        
    ll flag=0;
    while(suml!=sumr && s.empty()==0)
        {//cout<<"suml: "<<suml<<" sumr: "<<sumr<<endl;
        if(suml>sumr)
            {s1.push(s.top());
             s.pop();
             sumr+=s1.top();
             suml-=s1.top();
             
            }
        else    if(suml<sumr || s.empty()==1)
        {flag=1;
         //cout<<"break"<<endl;
        break;}
    }
    if(flag!=1 && suml==sumr)
        {//cout<<"return"<<s.size()<<endl;
        return s.size()+st;
    }
    
    }
        return 0;
    
    
    
}


ll part(ll st,ll en)
    {
    ll d=desti(st,en);
    
    if(d==0)
        return 0;
    /*if(d==-1)
        return -1;
   */     
        
    return max(1+part(st,d),1+part(d,en));
       
}
int main() {
    ll t;
    cin>>t;
    while(t--)
        {
        cin>>n;
        for(ll i=0;i<n;i++)
            {cin>>arr[i];}
        
       /* ll a=part(0,n);
        if(a==1 && suml==0)
            cout<<0;
        else
            cout<<a<<endl;
       */ 
        cout<<part(0,n)<<endl;
       //cout<< desti(0,n)<<endl;
    }
    
    /* Enter your code here. Read input from STDIN. Prll output to STDOUT */   
    return 0;
}

Nikita and the Game C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {
    static void Main(String[] args) {
        int t = int.Parse(Console.ReadLine());
        for(int i = 0; i<t; i++){
            TestCase();
        }        
    }
    
    static void TestCase(){
        int n = int.Parse(Console.ReadLine());
        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        long sum = 0;
        foreach(int i in a){
            sum+= i;
        }
        hash = new Dictionary<string, int>();
        
        Console.WriteLine(Score(a, 0, a.Length-1, sum));
    }
    
    static Dictionary<string, int> hash;
    
    static int Score(int[] a, int left, int right, long sum){
        string key = left + "," + right;
        if(hash.ContainsKey(key)){
            return hash[key];
        }
        
        if (right == left ){
            // can't partition single element
            return 0;
        }
        
        if (sum % 2 == 1)
        {
            // partition failed - sum is odd
            return 0;
        }
        
        long leftSum = a[left];
        int p = left;
        while(leftSum < sum/2){
            p++;
            leftSum+=a[p];
        }
        
        if (leftSum != sum/2){
            // partition failed to find equal halves
            return 0;
        }
        
        int result = 1 + Math.Max(Score(a, left, p, sum/2), Score(a, p+1, right, sum/2));
        hash[key] = result;
        return result;
    }
}

Nikita and the Game Java Solution

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

Nikita and the Game JavaScript Solution

process.stdin.resume();
process.stdin.setEncoding("ascii");
var input = "";
process.stdin.on("data", function (chunk) {
    input += chunk;
});
process.stdin.on("end", function () {
    // now we can read/parse input
 
    var arr = input.split("\n");
  
    cnt= parseInt(arr[0]);   // count of samples
   //  console.log(cnt);
    for(var e=0 ; e < arr.length-2; e=e+2)
    { 
         
        var sample = arr[e+2].split(" ");
  //       console.log(sample);
      var points= tryToSplit(sample);
      console.log(points);
    }
    
});

function tryToSplit (arr)
{
    var sum= 0;
    var tmp= 0;
    var i=0;

    for(i=0 ; i<arr.length;i++)
    {   sum += parseInt(arr[i]); }

    if (sum %2 || arr.length ==1 ) return 0;

    if (sum==0)
        return arr.length-1;
    
    for(i=0;i<arr.length;i++)
    {
       tmp+=parseInt(arr[i]);

        if (tmp == sum / 2)
        {
            var arr1= arr.slice(0,i +1);
            var arr2= arr.slice(i + 1 , arr.length);

            var pt1= tryToSplit(arr1);
            var pt2= tryToSplit(arr2);

            if (pt1 > pt2 )
            { 
                          
                return 1 +pt1;
                
            }
            else
            {                
                return 1 + pt2;
            }   

        }

        if (tmp> sum/2)
            return 0;
    }
}

Nikita and the Game Python Solution


def findSplit(A):
    Lsum = 0
    Lind = -1
    Rsum = 0
    Rind = len(A)
    splits = 0
    while Rind - Lind > 1:
        #print("intermediate",Lind,Rind,Lsum,Rsum)
        if(Lsum <= Rsum):
            Lind += 1
            Lsum += A[Lind]
        else:
            Rind -= 1
            Rsum += A[Rind]
           
    if(Rsum == Lsum):
        splits = 1
        Lsplits = 0
        Rsplits = 0
        if(Lind >= 1):
            #print("going left")
            if(Lsum != 0):
                Lsplits = findSplit(A[0:Lind+1])
            else:
                return len(A)-1
        if(Rind <= len(A)-2):
            #print("going right",A,Rind)
            Rsplits = findSplit(A[Rind:])
        splits += max(Lsplits,Rsplits)
    
    #print(A,Lind,Rind,Rsum,Lsum,splits)
    return splits
        



T = int(input())
for i in range(0,T):
    N = int(input())
    A = [int(x) for x in input().split()]
    print(findSplit(A))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python