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